Modular Arithmetic Summary

Number Theory · Axiom Academy

Let's review the fundamental concepts and techniques of arithmetic modulo n. Definition: a ≡ b (mod n ) means n divides a - b Equivalence Relation: Congruence satisfies reflexive, symmetric, and transitive properties Residue Classes: The integers modulo n form n equivalence classes: [0], [1], ..., [ n -1] Complete Residue System: A set containing exactly one element from each residue class mod n Addition: If a ≡ b and c ≡ d (mod n ), then a + c ≡ b + d (mod n ) Multiplication: If a ≡ b and c ≡ d (mod n ), then ac ≡ bd (mod n ) Powers: If a ≡ b (mod n ), then a k ≡ b k (mod n ) for any positive integer k Division Caution: Cannot simply divide both sides unless the divisor is coprime to the modulus Definition: a -1 is the modular inverse of a if aa -1 ≡ 1 (mod n ) Existence: a has a modular inverse mod n if and only if gcd(a, n) = 1 Finding Inverses: Use the Extended Euclidean Algorithm to find x and y where ax + ny = 1 Applications: Solving linear congruences, dividing in modular arithmetic, cryptography Statement: Given pairwise coprime moduli n 1 , ..., n k , the system x ≡ a i (mod n i ) has a unique solution modulo N = n 1 ...n k Construction: Set N i = N/n i , find M i where N i M i ≡ 1 (mod n i ), then x ≡ Σa i N i M i Why It Matters: Breaks complex problems into simpler subproblems with smaller moduli Computational Use: Fast exponentiation, RSA encryption, solving simultaneous congruences Example Recap: Solving a Linear Congruence Problem: Solve 17 x ≡ 5 (mod 31)

This is the written version of the interactive lesson above. See the full Number Theory course.