--- title: "Modular Arithmetic and Congruence Classes" description: "Agree to identify integers with the same remainder, check the arithmetic survives that identification, and compute in the resulting finite system." canonical: https://lightmysky.com/learn/mathematics/modular-arithmetic-and-congruence-classes-mt_Lt4_Aazx2j source: https://lightmysky.com/learn/mathematics/modular-arithmetic-and-congruence-classes-mt_Lt4_Aazx2j.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Mathematics · Area: Number Theory · Ages 19 to 20 Page: https://lightmysky.com/learn/mathematics/modular-arithmetic-and-congruence-classes-mt_Lt4_Aazx2j ## Ready when they can - 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 ## Lesson: Remainders you can add and multiply 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. *(drawing: Clock arithmetic wraps after 12. 12 plus 1 is 1 again, since times agree when they differ by a multiple of 12.)* 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. **Recap.** Identify integers by remainder, compute inside the finite system, and use missing residues to rule equations out. ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Euclid's Algorithm and Bezout's Identity](https://lightmysky.com/learn/mathematics/euclids-algorithm-and-bezouts-identity-mt_26hM0EnJpq) - [Equivalence Relations and Partitions](https://lightmysky.com/learn/mathematics/equivalence-relations-and-partitions-mt_wgEupYwEUF) ## Opens up - [Linear Congruences and the Chinese Remainder Theorem](https://lightmysky.com/learn/mathematics/linear-congruences-and-the-chinese-remainder-theorem-mt_J9_RMpwcRX) - [Hashes, Signatures and Certificates](https://lightmysky.com/learn/computing/hashes-signatures-and-certificates-mt_qLHm767U87)