Congruences
Modular inverses, the Chinese remainder theorem, and Fermat.
Pen and paper is fine · no calculator needed why?
Opens at level 44.
the lesson
Read the lesson
The idea
A congruence like x ≡ 3 (mod 5) says x leaves remainder 3 when divided by 5.
The inverse of a mod m is the whole number x with ax ≡ 1 (mod m). Euler's totient φ(n) counts the numbers from 1 to n that share no factor with n except 1. Fermat's little theorem gives a shortcut for big powers divided by a prime.
Techniques
List and test
- Inverse of a mod m: list m + 1, 2m + 1, 3m + 1 and so on.
- The first one that a divides, divided by a, is the inverse. For 3 mod 11: 12 ÷ 3 = 4.
- Two conditions: list the numbers that fit the larger modulus. Stop at the first that fits the other.
worked example
What is the smallest positive whole number x with x ≡ 2 (mod 3) and x ≡ 4 (mod 7)?
- Numbers leaving 4 when divided by 7: 4, 11, 18.
- 4 leaves 1 when divided by 3, and 11 leaves 2.
- So x is 11.
Answer: 11
Totient from the primes
- Find the different primes that divide n.
- Multiply n by (1 − 1/p) for each of those primes p.
- If n is prime, the answer is n − 1.
worked example
What is φ(40), the count of whole numbers from 1 to 40 that share no factor with 40 other than 1?
- 40 is 2³ × 5, so the primes are 2 and 5.
- 40 × 1/2 × 4/5 = 16.
Answer: 16
Fermat: shrink the exponent
- a to the power p − 1 leaves remainder 1, so every p − 1 in the exponent drops out.
- Divide the exponent by p − 1 and keep the remainder r.
- Work out a to the power r, and take its remainder by p.
worked example
What is 5⁶² mod 7? Give the remainder from 0 to 6.
- 7 is prime, so 5⁶ leaves remainder 1.
- 62 = 10 × 6 + 2, so 5⁶² leaves what 5² leaves.
- 25 = 3 × 7 + 4, so the answer is 4.
Answer: 4
Tips by skill
- TipModular inverse: List the numbers 1 more than a multiple of the modulus. The first one a divides, divided by a, is the inverse.
- TipEuler’s totient: Find the different primes dividing n. Multiply n by (1 − 1/p) for each one.
- TipTwo remainders at once: List the numbers that fit the larger modulus. The first that also fits the other condition is the answer.
- TipFermat’s little theorem: Only the exponent's remainder by p − 1 matters. Then work out that small power and take its remainder.
Watch out for
- Giving a fraction like 1/3 for an inverse. The inverse is a whole number from 1 to m − 1.
- Using n − 1 for φ(n) when n is not prime.
- Stopping at a solution that is not the smallest. Subtract the product of the two moduli.
- Reducing the exponent by p instead of p − 1 when using Fermat.
skills · practice stats
-
Modular inverse not tried yet
worked example
What is the inverse of 7 modulo 31? Give the whole number x from 1 to 30 with 7x ≡ 1 (mod 31).
Answer: 9
- Numbers 1 more than a multiple of 31: 32, 63. The first that divides by 7 is 63.
- 63 = 7 × 9, so 7 × 9 ≡ 1 (mod 31) and x = 9.
-
Euler’s totient not tried yet
worked example
What is φ(77)? φ(n) counts the whole numbers from 1 to n that share no factor with n other than 1.
Answer: 60
- 77 = 7 × 11.
- φ(77) = 77 × (1 − 1/7) × (1 − 1/11) = 77 × 6/7 × 10/11 = 60.
-
Two remainders at once not tried yet
worked example
What is the smallest positive whole number x with x ≡ 2 (mod 5) and x ≡ 2 (mod 3)?
Answer: 2
- List the numbers that leave 2 when divided by 5: 2.
- The first of them that leaves 2 when divided by 3 is 2 (2 = 0 × 3 + 2).
- So x = 2.
-
Fermat’s little theorem not tried yet
worked example
What is 6²³⁶ mod 7? Give the remainder from 0 to 6.
Answer: 1
- Fermat: 7 is prime and doesn't divide 6, so 6⁶ ≡ 1 (mod 7).
- 236 = 39 × 6 + 2, so 6²³⁶ ≡ 6² (mod 7).
- Powers of 6 leave 6, 1 when divided by 7, so 6² ≡ 1.
rest ladder
- 1 day
- 3 days
- 7 days
- 14 days
- 30 days
- 60 days
- mastered · every 90 days