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 m consists of systematically replacing the results of additions, multiplications, and subtractions by the remainder of the division by m. A remarkable property of modular arithmetic is that the result of a computation does not depend on whether the division by m 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 7 + 8 = 15, 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).
Congruence Given an integer m ≥ 1, called a modulus, two integers a and b are said to be congruent modulo m, if their difference a − b is an integer multiple of m; that is, if there is an integer k such that
a − b = km. Congruence modulo m is a congruence relation, meaning that it is an equivalence relation compatible with addition, subtraction, and multiplication. Congruence modulo m is denoted by
a ≡ b ( mod m ) . {\displaystyle a\equiv b{\pmod {m}}.}
The parentheses mean that (mod m) applies to the entire equation, not just to the right-hand side (here, b). This notation is not to be confused with the notation b mod m or (b mod m) (without parentheses immediately before "mod"), which refers to the remainder of b when divided by m, known as the modulo operation; that is, b mod m denotes the unique integer r such that 0 ≤ r < m and r ≡ b (mod m). So, the relation a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} must be read ( a ≡ b ) mod m , {\displaystyle (a\equiv b){\bmod {m}},} and is equivalent with a mod m = b mod m . {\displaystyle a{\bmod {m}}=b{\bmod {m}}.}
The congruence relation a ≡ b (mod m) may be rewritten as
∃ k ∈ Z a = k m + b , {\displaystyle \exists k\in \mathbb {Z} \quad a=km+b,}
explicitly showing its relationship with Euclidean division. However, the b here need not be the remainder in the division of a by m. Rather, a ≡ b (mod m) asserts that a and b have the same remainder when divided by m. That is,
a = p m + r, b = q m + r, where 0 ≤ r < m is the common remainder. We recover the previous relation (a − b = k m) by subtracting these two expressions and setting k = p − q. Because the congruence modulo m is defined by the divisibility by m and because −1 is a unit in the ring of integers, a number is divisible by −m exactly if it is divisible by m. This means that every non-zero integer m may be taken as a modulus.
Examples In modulus 12, one can assert that:
38 ≡ 14 (mod 12) because the difference is 38 − 14 = 24 = 2 × 12, a multiple of 12. Equivalently, 38 and 14 have the same remainder 2 when divided by 12. The definition of congruence also applies to negative values. For example:
2 ≡ − 3 ( mod 5 ) − 8 ≡ + 7 ( mod 5 ) − 3 ≡ − 8 ( mod 5 ) . {\displaystyle {\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv {\phantom {+}}7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}
Basic properties
The congruence relation satisfies all the conditions of an equivalence relation:
Reflexivity: a ≡ a (mod m) Symmetry: a ≡ b (mod m) if and only if b ≡ a (mod m). Transitivity: If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m) If a1 ≡ b1 (mod m) and a2 ≡ b2 (mod m), or if a ≡ b (mod m), then:
… excerpt ends here. Continue reading the full article.
