Modular arithmetic is arithmetic that wraps around after reaching a fixed number called the modulus. It is the math behind clocks, calendars, repeating patterns, and many digital systems. Instead of keeping every integer distinct, modular arithmetic groups numbers by the remainder they leave after division.
This makes it a powerful way to study cycles and repeated behavior.
Key Facts
- a ≡ b mod n means n divides a - b.
- The possible residues mod n are 0, 1, 2, ..., n - 1.
- To add modulo n, add normally and take the remainder: (a + b) mod n.
- To multiply modulo n, multiply normally and take the remainder: (ab) mod n.
- If a ≡ b mod n and c ≡ d mod n, then a + c ≡ b + d mod n and ac ≡ bd mod n.
- Clock example: 8 + 7 = 15, and 15 ≡ 3 mod 12, so 8 + 7 ≡ 3 mod 12.
Vocabulary
- Modulus
- The modulus is the positive integer that sets the size of the repeating cycle in modular arithmetic.
- Residue
- A residue is the remainder left after dividing an integer by the modulus.
- Congruence
- Congruence means two integers have the same remainder when divided by the same modulus.
- Remainder
- The remainder is the amount left over after division by a whole number.
- Check digit
- A check digit is an extra digit calculated with arithmetic rules to help detect errors in numbers such as barcodes or identification codes.
Common Mistakes to Avoid
- Writing a ≡ b mod n when a and b only look close. Congruence depends on whether a - b is divisible by n, not on how near the numbers are.
- Forgetting to reduce the final answer. In modular arithmetic, answers are usually written as residues from 0 to n - 1.
- Treating division like ordinary division modulo n. Modular division only works when the divisor has a multiplicative inverse modulo n.
- Using the wrong modulus in a clock problem. A 12-hour clock uses mod 12 for hour positions, while a 24-hour clock uses mod 24.
Practice Questions
- 1 Compute 19 + 28 mod 12 and write the answer as a residue from 0 to 11.
- 2 Compute 7 × 9 mod 13.
- 3 A check digit system uses remainders mod 10. Explain why two numbers that differ by a multiple of 10 would have the same check digit in this simple system.