Number Theory: Modular Arithmetic
Modular arithmetic, often called “clock arithmetic,” is a system of arithmetic for integers, where numbers wrap around after reaching a certain value, known as the modulus.
Basic Definitions
For a positive integer n, we say two integers a and b are congruent modulo n if n divides their difference:
a ≡ b (mod n) ⇔ n | (a − b)Examples:
- 7 ≡ 2 (mod 5) because 7−2 = 5.
- −3 ≡ 2 (mod 5) because −3−2 = −5.
Key Properties
- Addition:
(a + b) mod n = ((a mod n) + (b mod n)) mod n - Multiplication:
(a·b) mod n = ((a mod n)·(b mod n)) mod n - Exponentiation: Use repeated squaring with modulo at each step.
Applications
Modular arithmetic underpins many areas:
- Cryptography (RSA, Diffie‑Hellman)
- Hash functions
- Computer algorithms (e.g., checking divisibility)
- Calendars and time calculations
Example: Solving Linear Congruences
Find all x such that 4x ≡ 6 (mod 10).
First reduce the equation by dividing by the gcd(4,10)=2:
2x ≡ 3 (mod 5)Now find the modular inverse of 2 modulo 5, which is 3 because 2·3 ≡ 1 (mod 5). Multiply both sides:
x ≡ 3·3 ≡ 9 ≡ 4 (mod 5)Thus the solutions are x ≡ 4 (mod 5), i.e., x = 4, 9, 14, …