Modular arithmetic is a way to do math with repeating cycles, such as hours on a clock, days of the week, or positions around a wheel. Instead of keeping the full value of a number, we focus on its remainder after division by a chosen modulus. This makes large numbers easier to compare and is useful in calendars, cryptography, computer science, and number theory.
Congruences give a precise language for saying that two numbers land in the same place in a cycle.
Key Facts
- a ≡ b mod n means n divides a - b.
- a mod n is the remainder when a is divided by n, usually chosen from 0 to n - 1.
- If a ≡ b mod n and c ≡ d mod n, then a + c ≡ b + d mod n.
- If a ≡ b mod n and c ≡ d mod n, then ac ≡ bd mod n.
- To reduce a large expression mod n, reduce each part first, then combine the remainders.
- The linear congruence ax ≡ b mod n has a solution only if gcd(a, n) divides b.
Vocabulary
- Modulus
- The modulus is the positive integer n that sets the cycle length in modular arithmetic.
- Remainder
- The remainder is what is left after dividing an integer by the modulus.
- Congruent
- Two integers are congruent modulo n if they have the same remainder when divided by n.
- Residue
- A residue is a representative remainder value for a congruence class modulo n.
- Linear Congruence
- A linear congruence is an equation of the form ax ≡ b mod n, where x is the unknown integer.
Common Mistakes to Avoid
- Treating a ≡ b mod n as ordinary equality is wrong because congruence means the numbers differ by a multiple of n, not that they are identical.
- Forgetting to reduce negative numbers correctly is wrong because the standard remainder should usually be between 0 and n - 1, such as -3 ≡ 9 mod 12.
- Canceling factors without checking is wrong because division in modular arithmetic is only valid when the factor has a multiplicative inverse modulo n.
- Assuming every congruence ax ≡ b mod n has one solution is wrong because solutions depend on gcd(a, n), and there may be no solution or multiple solutions.
Practice Questions
- 1 Find the least nonnegative residue of 137 mod 12, then explain where 137 lands on a mod 12 clock.
- 2 Solve the congruence 5x ≡ 3 mod 7 for x in the set {0, 1, 2, 3, 4, 5, 6}.
- 3 Explain why 26, 50, and 74 are all congruent modulo 24, and describe what that means on a 24-hour clock.