Finding something worth knowing…

Science

Clock math is modular arithmetic in plain sight

Modular arithmetic lets integers wrap around a chosen modulus, the way a 12-hour clock turns 7 plus 8 into 3 instead of 15. Carl Friedrich Gauss systematized the modern number-theoretic approach in Disquisitiones Arithmeticae. Remainders become a parallel universe of addition and multiplication.

Working modulo m means replacing results of sums, products and differences with remainders on division by m. Order of reduction is forgiving: you may reduce after every step, only at the end, or whenever an intermediate number grows unwieldy, and still land on the same answer. On a clock, twelve behaves like zero, written 12 ≡ 0 (mod 12), and two waits of eight hours move the hand exactly as one four-hour wait does, mirroring 2 × 8 ≡ 4 (mod 12). Gauss laid out this approach to number theory in 1801.

Formally, integers a and b match modulo m when their difference is a multiple of m, which is the same as saying they leave the same remainder. So 38 and 14 agree modulo 12, since 38 minus 14 is 24, twice twelve, and both leave 2. Negative numbers obey the same rule: 2 ≡ −3 and −8 ≡ 7 modulo 5. Because divisibility by m and by −m coincide, any nonzero integer can serve as a modulus.

Notation matters. Writing (mod m) in parentheses applies the modulus to the whole statement, whereas b mod m without them names a single number, the remainder r with 0 ≤ r < m. The relation is reflexive, symmetric and transitive, and it survives shifting, scaling, adding, subtracting, multiplying, raising to powers and plugging into any polynomial with integer coefficients.

Cancelling needs care. You may drop a common added term freely, but you may divide out a common factor k only when k shares no divisor with m. Likewise a number has a multiplicative inverse modulo m, some partner whose product with it is congruent to 1, exactly when the two are coprime. A congruence modulo mn also holds modulo m and modulo n separately.

Source: Modular arithmetic

Related

More in Science · All topics