courses › Number Theory

Modular inverses, the Chinese remainder theorem, and Fermat.

Pen and paper is fine · no calculator needed why?

Learn first (about 3 minutes)

Opens at level 44.

Sign in to start

Builds on: Clock arithmetic (not open yet)

skills · practice stats

From rounds of this course only: box, review and trial answers are left out. Once a skill has 40 tries, it compares your first 20 tries with your last 20.

• Modular inverse par 25 s 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

  1. Numbers 1 more than a multiple of 31: 32, 63. The first that divides by 7 is 63.
  2. 63 = 7 × 9, so 7 × 9 ≡ 1 (mod 31) and x = 9.

• Euler’s totient par 25 s 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

  1. 77 = 7 × 11.
  2. φ(77) = 77 × (1 − 1/7) × (1 − 1/11) = 77 × 6/7 × 10/11 = 60.

• Two remainders at once par 40 s 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

  1. List the numbers that leave 2 when divided by 5: 2.
  2. The first of them that leaves 2 when divided by 3 is 2 (2 = 0 × 3 + 2).
  3. So x = 2.

• Fermat’s little theorem par 30 s not tried yet

  worked example

  What is 6²³⁶ mod 7? Give the remainder from 0 to 6.

  Answer: 1

  1. Fermat: 7 is prime and doesn't divide 6, so 6⁶ ≡ 1 (mod 7).
  2. 236 = 39 × 6 + 2, so 6²³⁶ ≡ 6² (mod 7).
  3. Powers of 6 leave 6, 1 when divided by 7, so 6² ≡ 1.

rest ladder

Win 3 of your last 4 rounds and the course rests. A win is 90% right, within 2× the round's par. Pass the review when it comes back and the next rest is longer.

1. 1 day
2. 3 days
3. 7 days
4. 14 days
5. 30 days
6. 60 days
7. mastered · every 90 days

your rounds

No rounds yet.