Modular arithmetic partitions integers into equivalence classes. For example, mod 12 gives us clock arithmetic (17:00 ≡ 5:00). The concept connects to solving equations but in a finite number system.
Modular Operations
(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a · b) mod m = ((a mod m) · (b mod m)) mod m
aⁿ mod m → use repeated squaring (fast exponentiation)
The modular inverse of a (mod m) is x such that a·x ≡ 1 (mod m). It exists if and only if GCD(a, m) = 1 (a and m are coprime). Found via the Extended Euclidean Algorithm — see GCD computation.
This is essential for division in modular arithmetic and for RSA decryption.
Fermat & Euler
Fermat's Little Theorem: aᵖ⁻¹ ≡ 1 (mod p) if p is prime and gcd(a,p) = 1
Euler's Theorem: a^φ(n) ≡ 1 (mod n) if gcd(a,n) = 1
Euler's totient: φ(n) = n · ∏(1 − 1/p) for each prime p dividing n
Fermat's theorem is a special case of Euler's (since φ(p) = p − 1). These are the theoretical backbone of RSA encryption. The exponential functions connect to the structure of multiplicative groups mod n.
Chinese Remainder Theorem
If m₁, m₂, …, mₖ are pairwise coprime, then:
x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₖ (mod mₖ)
has a unique solution mod (m₁·m₂·…·mₖ)
CRT says you can reconstruct a number from its remainders — like reassembling a puzzle from pieces. This has applications in computer science (parallel computation), cryptography (speeding up RSA), and even calendar calculations.