--- 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-09-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. **Example.** 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. **Tip.** 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. **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)