Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Simple addition would result in 7 + 8 = 15, but clocks "wrap around" every 12 hours. Because the hour number starts over at zero when it reaches 12, this is arithmetic modulo 12. In terms of the definition below, 15 is congruent to 3 modulo 12, so "15:00" on a 24-hour clock is displayed "3:00" on a 12-hour clock. Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference (that is, if there is an integer k such that a − b = kn). Congruence modulo n is a congruence relation, meaning that it is an equivalence relation that is compatible with the operations of addition, subtraction, and multiplication. Congruence modulo n is denoted: The parentheses mean that (mod n) 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 n (without parentheses), which refers to the modulo operation. Indeed, b mod n denotes the unique integer a such that 0 ≤ a < n and (that is, the remainder of when divided by ). The congruence relation may be rewritten as explicitly showing its relationship with Euclidean division. However, the b here need not be the remainder of the division of a by n. Instead, what the statement a ≡ b (mod n) asserts is that a and b have the same remainder when divided by n. That is, where 0 ≤ r < n is the common remainder. Subtracting these two expressions, we recover the previous relation: by setting k = p − q. In modulus 12, one can assert that: because 38 − 14 = 24, which is a multiple of 12.