Modular arithmetic ================== In mathematics, modular arithmetic is a system of arithmetic operations for integers, differing from the usual ones in that numbers "wrap around" when reaching or exceeding a certain value, called the modulus. The modern approach to number theory using modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. Modular arithmetic modulo consists of systematically replacing the results of additions, multiplications, and subtractions by the remainder of the division by . A remarkable property of modular arithmetic is that the result of a computation does not depend on whether the division by is performed after each operation, only once at the end of the computation, or at the end of the computation and after some intermediate results typically when an intermediate result becomes too large. In mathematics, modular arithmetic is a system of arithmetic operations for integers, differing from the usual ones in that numbers "wrap around" when reaching or exceeding a certain value, called the modulus. The modern approach to number theory using modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. Modular arithmetic modulo consists of systematically replacing the results of additions, multiplications, and subtractions by the remainder of the division by . A remarkable property of modular arithmetic is that the result of a computation does not depend on whether the division by is performed after each operation, only once at the end of the computation, or at the end of the computation and after some intermediate results typically when an intermediate result becomes too large. ==Motivating example== A familiar setting exhibiting modular arithmetic is the hour hand on a 12-hour clock. If the hour hand points to 7 now, then 8 hours later it will point to 3. Ordinary addition would result in , but 15 reads as 3 on the clock face. This is because the hour hand makes one rotation every 12 hours and the hour number starts over when the hour hand passes 12. We say that 15 is congruent to 3 modulo 12, and we write 15 ≡ 3 (mod 12), so 7 + 8 ≡ 3 (mod 12). Similarly, if one waits 8 hours and then 8 more hours (thus 16 hours in total), the clock will show the same time change as if one waited 4 hours. This is reflected by the identity 2 × 8 ≡ 4 (mod 12). After a wait of exactly 12 hours, the hour hand will be right where it started, so 12 acts as 0; one writes 12 ≡ 0 (mod 12). This notation is not to be confused with the notation or (without parentheses immediately before "mod"), which refers to the remainder of when divided by , known as the modulo operation; that is, denotes the unique integer such that and . So, the relation a \equiv b \pmod m must be read (a \equiv b) \bmod m, and is equivalent with a\bmod m = b\bmod m. The congruence relation may be rewritten as \exists k\in\Z\quad a=km+b, explicitly showing its relationship with Euclidean division. However, the here need not be the remainder in the division of by Rather, asserts that and have the same remainder when divided by . That is, , , where is the common remainder. We recover the previous relation ( ) by subtracting these two expressions and setting Because the congruence modulo is defined by the divisibility by and because is a unit in the ring of integers, a number is divisible by exactly if it is divisible by . This means that every non-zero integer may be taken as a modulus. == Congruence classes == The congruence relation is an equivalence relation. The equivalence class modulo of an integer is the set of all integers of the form , where is any integer. It is called the congruence class or residue class of modulo  , and may be denoted , or as or when the modulus is known from the context. Each residue class modulo  contains exactly one integer in the range 0, ..., |m| - 1 . Thus, these |m| integers are representatives of their respective residue classes. It is generally easier to work with integers than sets of integers; that is, the representatives most often considered, rather than their residue classes. Consequently, denotes generally the unique integer such that and ; it is called the residue of modulo  . In particular, is equivalent to , and this explains why " " is often used instead of " " in this context. The set of all congruence classes modulo is a ring called the ring of integers modulo , and is denoted \mathbb{Z}/m\mathbb{Z} , \mathbb{Z}/(m) , \mathbb{Z}/m , or \mathbb{Z}_m . The ring \mathbb{Z}/m\mathbb{Z} is fundamental to various branches of mathematics (see below). (In some parts of number theory the notation \mathbb{Z}_m is avoided because it can be confused with the set of -adic integers.) For one has \mathbb{Z}/m\mathbb{Z} = \left\{ \overline{a}_m \mid a \in \mathbb{Z}\right\} = \left\{ \overline{0}_m, \overline{1}_m, \overline{2}_m,\ldots, \overline{m{-}1}_m \right\}. When , \mathbb{Z}/m\mathbb{Z} is the zero ring; when , \mathbb{Z}/m\mathbb{Z} is not an empty set; rather, it is isomorphic to \mathbb{Z} , since . Addition, subtraction, and multiplication are defined on \mathbb{Z}/m\mathbb{Z} by the following rules: \overline{a}_m + \overline{b}_m = \overline{(a + b)}_m \overline{a}_m - \overline{b}_m = \overline{(a - b)}_m \overline{a}_m \overline{b}_m = \overline{(a b)}_m. The properties given before imply that, with these operations, \mathbb{Z}/m\mathbb{Z} is a commutative ring. For example, in the ring \mathbb{Z}/24\mathbb{Z} , one has \overline{12}_{24} + \overline{21}_{24} = \overline{33}_{24}= \overline{9}_{24} as in the arithmetic for the 24-hour clock. The notation \mathbb{Z}/m\mathbb{Z} is used because this ring is the quotient ring of \mathbb{Z} by the ideal m\mathbb{Z} , the set formed by all multiples of , that is, all numbers with k\in\mathbb{Z}. Under addition, \mathbb Z/m\Z is a cyclic group. All finite cyclic groups are isomorphic with \mathbb Z/m\mathbb Z for some . The ring of integers modulo is a field; that is, every nonzero element has a multiplicative inverse, if and only if is prime. If is a prime power with , there exists a unique (up to isomorphism) finite field \mathrm{GF}(m) =\mathbb F_m with elements, which is not isomorphic to \mathbb Z/m\mathbb Z , which fails to be a field because it has zero-divisors. If , (\mathbb Z/m\mathbb Z)^\times denotes the multiplicative group of the integers modulo that are invertible. It consists of the congruence classes , where is coprime to ; these are precisely the classes possessing a multiplicative inverse. They form an abelian group under multiplication; its order is , where is Euler's totient function. The use of long division to turn a fraction into a repeating decimal in any base b is equivalent to modular multiplication of b modulo the denominator. For example, for decimal, b = 10. In music, arithmetic modulo 12 is used in the consideration of the system of twelve-tone equal temperament, where octave and enharmonic equivalency occurs (that is, pitches in a 1:2 or 2:1 ratio are equivalent, and C-sharp is considered the same as D-flat). The method of casting out nines offers a quick check of decimal arithmetic computations performed by hand. It is based on modular arithmetic modulo 9, and specifically on the crucial property that 10 ≡ 1 (mod 9). Arithmetic modulo 7 is used in algorithms that determine the day of the week for a given date. In particular, Zeller's congruence and the Doomsday algorithm make heavy use of modulo-7 arithmetic. More generally, modular arithmetic also has application in disciplines such as politics (for example, apportionment), economics (for example, game theory) and other areas of the social sciences, where proportional division and allocation of resources plays a central part of the analysis. REFERENCES ---------- [1] Wikipedia BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Modular arithmetic}, url = {https://encyclopegia.org/a/modular-arithmetic} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Modular arithmetic UR - https://encyclopegia.org/a/modular-arithmetic ER - CITE THIS ARTICLE ---------------- Cite this article: Modular arithmetic Derived from: https://en.wikipedia.org/w/index.php?oldid=1378015346 Licence: CC BY-SA 4.0 Snapshot: enwiki-001378015346 Permalink: /a/modular-arithmetic