Fermat's Little Theorem and Euler's Theorem · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Shortcuts for giant modular powers

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

  1. What is 2^10 modulo 11?

    • 1
    • 2
    • 10
    • 0

  2. How many integers from 1 to 9 are coprime to 9? That is, what is phi(9)?

    Answer: ______________

  3. What is 2 to the 10th modulo 11?

    • 2
    • 1
    • 10

  4. What is phi of 12?

    • 4
    • 6
    • 12

  5. Ana says multiplying every nonzero remainder mod 7 by 3 just reshuffles the list 1, 2, 3, 4, 5, 6.

    Circle one:   True   False

  6. What is 4^5 modulo 5?

    • 4
    • 1
    • 0
    • 2

  7. What is 3^100 modulo 7?

    Answer: ______________

  8. What is 3 to the 100th modulo 7?

    Answer: ______________

  9. What is 5 to the 61st modulo 7?

    • 5
    • 1
    • 6

  10. A student reduces 3 to the 100th modulo 7 by replacing 100 with its remainder modulo 7. What is wrong?

    • Exponents can never be reduced at all
    • 100 is already small enough to compute
    • Exponents shrink modulo phi of n, which is 6, not 7
LightMySky · lightmysky.comW1-mt_7wW4z4Eidx-s1

Answer key

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

Shortcuts for giant modular powers W1-mt_7wW4z4Eidx-s1

  1. 1 · 11 is prime and does not divide 2, so Fermat gives 2^10 ≡ 1 (mod 11).
  2. 6 · The numbers below 9 that share no factor with 9 are 1, 2, 4, 5, 7, 8. There are 6 of them, so phi(9) = 6.
  3. 1 · 11 is prime and skips 2, so Fermat gives remainder 1.
  4. 4 · The numbers below 12 coprime to 12 are 1, 5, 7, 11.
  5. True · Since 3 is coprime to 7, multiplication by 3 permutes the residues.
  6. 4 · Fermat gives 4^4 ≡ 1 (mod 5), so 4^5 = 4 times 4^4 ≡ 4 (mod 5).
  7. 4 · phi(7) = 6, and 100 = 16 times 6 plus 4, so 3^100 ≡ 3^4 = 81 ≡ 4 (mod 7).
  8. 4 · Phi of 7 is 6, 100 leaves remainder 4, and 3 to the 4th is 4 modulo 7.
  9. 5 · Phi of 7 is 6, 61 leaves remainder 1, so the answer is 5.
  10. Exponents shrink modulo phi of n, which is 6, not 7 · The exponent lives modulo the totient, not modulo the base modulus.
Worksheet · LightMySky