Modular Arithmetic and Congruence Classes
Agree to identify integers with the same remainder, check the arithmetic survives that identification, and compute in the resulting finite system.
What a learner can do afterwards
- Show that addition and multiplication are well defined on congruence classes
- Compute a large power modulo n by repeated squaring
- Use a modulus to prove a divisibility claim or to rule out an equation having integer solutions
1 · Read
Modular arithmetic identifies integers that share a remainder. We write a is b mod n when n divides their difference, so 17 is 5 mod 6. Addition and multiplication stay consistent: you may swap any number for another with the same remainder. So 7 plus 9 mod 5 is 16 mod 5, which is 1, and 4 times 6 mod 7 is 24 mod 7, which is 3. One quirk: mod 6, 2 times 3 is 0, though neither factor is 0.
Large powers stay cheap through repeated squaring with reduction at each step. For 2 to the 10th mod 7, first get 2 to the 5th, which is 32, reducible to 4. Then square: 4 squared is 16, which reduces to 2. The same staging gives 3 to the 6th mod 7: cube to 27, reduce to 6, then square 36 down to 1. Reduce early and the numbers stay small.
Clock arithmetic is remainders in disguise. After 12 comes 1 again, since times agree when they differ by a multiple of 12. Modular arithmetic generalises the clock to any modulus. Prime moduli give the cleanest systems, while composite ones admit quirks like 2 times 3 is 0 mod 6. The clock picture keeps the wrap idea visible.
A modulus can prove an equation has no integer solutions. List every residue and check which ones the equation would need. Squares mod 4 are only 0 and 1, since 0, 1, 4, 9 leave remainders 0, 1, 0, 1. Remainder 2 never occurs, so x squared is 2 mod 4 is impossible. A missing residue rules the equation out.
Identify integers by remainder, compute inside the finite system, and use missing residues to rule equations out.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.