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.
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.
Stage 3 to the 6th as a cube then a square. 3 cubed is 27, which is 6 mod 7. Square 6 to get 36, which is 1 mod 7. Cubing then squaring keeps every number small.
Rule out solutions by listing residues. Work out every residue mod n, find which ones the equation needs, and show the needed one never occurs. One missing residue ends the search.
Identify integers by remainder, compute inside the finite system, and use missing residues to rule equations out.
Modular-arithmetic questions x3 through x6 are original in-repo writing; the x1 x2 items adapt Contemporary Mathematics material with unknown license terms. The rewritten readings were written for this dataset.
2 · Watch
Take it off screen
Where it sits
14 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.