Linear Congruences and the Chinese Remainder Theorem · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Solving congruences and combining remainders

Mathematics · Number Theory · ages 19-20
Name ______________________   Date ____________

  1. Find the smallest positive integer x with x ≡ 2 (mod 3) and x ≡ 3 (mod 5).

    Answer: ______________

  2. What is the inverse of 3 modulo 7? That is, which number times 3 leaves remainder 1 on division by 7?

    • 5
    • 3
    • 4
    • 6

  3. What is the inverse of 3 modulo 7? That is, which number times 3 leaves remainder 1 on division by 7?

    • 4
    • 2
    • 5

  4. Find the smallest positive integer x with x is 1 mod 4 and x is 2 mod 5. Give a number.

    Answer: ______________

  5. Find the smallest positive integer x with x ≡ 1 (mod 4) and x ≡ 2 (mod 5).

    Answer: ______________

  6. Sam says that x is 2 mod 5 and x is 4 mod 7 pin down x modulo 35. Is Sam right?

    Circle one:   True   False

  7. Priya says the congruence 2x ≡ 3 (mod 6) has no solution because 2 and 6 share a factor that does not divide 3. Is Priya right?

    Circle one:   True   False

  8. Sam says that x ≡ 2 (mod 5) and x ≡ 4 (mod 7) pin down x modulo 35. Is Sam right?

    Circle one:   True   False

  9. How many solutions does 6x ≡ 9 (mod 15) have modulo 15?

    Answer: ______________

  10. How many solutions does 6x is 9 mod 15 have modulo 15? Give a number.

    Answer: ______________

LightMySky · lightmysky.comW1-mt_J9_RMpwcRX-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Solving congruences and combining remainders W1-mt_J9_RMpwcRX-s1

  1. 8 · Numbers that are 3 mod 5 go 3, 8, 13. Of these, 8 is the first that is 2 mod 3, so 8 is the smallest positive solution.
  2. 5 · 3 times 5 is 15, and 15 leaves remainder 1 on division by 7, so 5 is the inverse of 3 modulo 7.
  3. 5 · 5 times 3 is 15, and 15 leaves remainder 1 on division by 7.
  4. 17 · List numbers 1 mod 4 and take the first that is 2 mod 5: 17.
  5. 17 · Numbers that are 2 mod 5 go 2, 7, 12, 17. Their remainders mod 4 are 2, 3, 0, 1, so 17 is the first that works.
  6. True · 5 and 7 are coprime, so the pair pins x down modulo 35.
  7. True · Priya is right. A congruence ax ≡ b (mod n) needs gcd(a, n) to divide b, but gcd(2, 6) = 2 does not divide 3.
  8. True · Sam is right. Moduli 5 and 7 are coprime, so the pair of conditions fixes x modulo 5 times 7 = 35.
  9. 3 · gcd(6, 15) = 3, and 3 divides 9, so there are exactly 3 solutions modulo 15.
  10. 3 · gcd(6, 15) is 3, and 3 divides 9, so there are exactly 3 solutions modulo 15.
Worksheet · LightMySky