Clock arithmetic: remainders and modular arithmetic

前置知识

4 项必需的前置知识（一直追溯到底）

你将学会

• Compute sums and products modulo n using remainders, for example on a 12-hour clock or in a 7-day week.
• Build addition and multiplication tables modulo n and look for patterns, such as which remainders have a multiplicative partner.
• Explain why the remainder of a sum or product depends only on the remainders of its parts.

定义

• a mod n is the remainder r, with 0 ≤ r < n, when a is divided by n.
• Addition modulo n: add as usual and take the remainder on division by n; multiplication modulo n works the same way.

定理

• (a + b) mod n = ((a mod n) + (b mod n)) mod n, and similarly for multiplication.
• A remainder a has a partner b with ab mod n = 1 exactly when a and n have no common factor greater than 1 (proved later with Euclid's algorithm).
• Modulo a prime p, every non-zero remainder has such a partner.

常见误解

• Thinking modular arithmetic is only about 12-hour clocks.
• Believing that if ab mod n = 0 then a or b must be 0 mod n; in fact 3 × 4 mod 12 = 0.
• Forgetting that a remainder must lie between 0 and n − 1.

通向

可选发现

• Congruences Clock arithmetic becomes the theory of congruences: a ≡ b (mod n) when n divides a − b, an equivalence relation that respects + and ×.探奇小径 →
• Groups The hours of a 12-hour clock under addition form a cyclic group of order 12.探奇小径 →
• Cryptography Fast modular exponentiation is the engine of RSA and Diffie–Hellman key exchange.
• ← Patterns
• ← Secret codes
• ← Integers