Discrete Math · Undergraduate

Fermat's Little Theorem and Euler's Theorem

Quick answer

Fermat's little theorem says that if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Euler's theorem extends it to any modulus: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). So to reduce a huge power, divide the exponent by p − 1 or φ(n) and keep only the remainder. 3¹⁰⁰ mod 7 becomes 3⁴ mod 7 = 4. The theorems also give inverses, a⁻¹ ≡ a^(p−2), and they are the reason RSA decryption works.

What you'll learn

  • State Fermat's little theorem and Euler's theorem
  • Reduce large exponents modulo p − 1 or φ(n)
  • Find last digits of large powers
  • Find modular inverses with a^(p−2)

Powers come back to 1

Fermat’s little theorem. If pp is prime and p∤ap \nmid a, then

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

Euler’s theorem. If gcd⁡(a,n)=1\gcd(a, n) = 1, then aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod{n}, with φ\varphi the totient. For a prime, φ(p)=p−1\varphi(p) = p - 1, so Fermat is the special case.

To reduce aka^k, write k=q⋅φ(n)+rk = q \cdot \varphi(n) + r. Then ak=(aφ(n))qar≡ara^k = \left(a^{\varphi(n)}\right)^q a^r \equiv a^r.

Why the powers return to 1

List the φ(n)\varphi(n) residues r1,…,rmr_1, \ldots, r_m coprime to nn. Multiplying each by aa gives ar1,…,armar_1, \ldots, ar_m, which are again coprime to nn and all different, since aa has an inverse mod nn. So the second list is the first list reordered, and their products agree: amr1⋯rm≡r1⋯rma^m r_1 \cdots r_m \equiv r_1 \cdots r_m. Cancelling the product, which is coprime to nn, leaves aφ(n)≡1a^{\varphi(n)} \equiv 1. The same fact is Lagrange’s theorem for the group of units mod nn.

Worked examples

Common mistakes

Practice problems

  1. Find 2101 mod 112^{101} \bmod 11.

    Answer

    22

    Full solution

    210≡12^{10} \equiv 1 and 101=10⋅10+1101 = 10 \cdot 10 + 1.

  2. Find 351 mod 73^{51} \bmod 7.

    Answer

    66

    Full solution

    51=6⋅8+351 = 6 \cdot 8 + 3, and 33=27≡63^3 = 27 \equiv 6.

  3. Find 538 mod 135^{38} \bmod 13.

    Answer

    1212

    Full solution

    38=12⋅3+238 = 12 \cdot 3 + 2, and 52=25≡125^2 = 25 \equiv 12.

  4. Find 625 mod 116^{25} \bmod 11.

    Answer

    1010

    Full solution

    25=10⋅2+525 = 10 \cdot 2 + 5, and 65=7776=11⋅706+106^5 = 7776 = 11 \cdot 706 + 10.

  5. Find the last digit of 320253^{2025}.

    Answer

    33

    Full solution

    φ(10)=4\varphi(10) = 4 and 2025=4⋅506+12025 = 4 \cdot 506 + 1, so 32025≡313^{2025} \equiv 3^1.

  6. Use 353^{5} to find the inverse of 33 modulo 77.

    Answer

    55

    Full solution

    3−1≡37−2=243=7⋅34+53^{-1} \equiv 3^{7-2} = 243 = 7 \cdot 34 + 5. Check: 3⋅5=15≡13 \cdot 5 = 15 \equiv 1.

  7. Find 3100 mod 1003^{100} \bmod 100.

    Answer

    11

    Full solution

    gcd⁡(3,100)=1\gcd(3, 100) = 1 and φ(100)=40\varphi(100) = 40, so 3100≡3203^{100} \equiv 3^{20}. Then 310=59049≡493^{10} = 59049 \equiv 49 and 492=2401≡149^2 = 2401 \equiv 1.

  8. A student reasons that 45≡1(mod6)4^5 \equiv 1 \pmod 6, since 6−1=56 - 1 = 5. Find 45 mod 64^5 \bmod 6.

    Answer

    44

    Full solution

    66 is not prime and gcd⁡(4,6)=2\gcd(4, 6) = 2. In fact 42=16≡44^2 = 16 \equiv 4, so every power of 44 is 44 mod 66.

Frequently asked questions

What does Fermat's little theorem say?

If p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Equivalently, aᵖ ≡ a (mod p) for every integer a.

What does Euler's theorem say?

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), where φ is Euler's totient.

How do I compute 3¹⁰⁰ mod 7?

3⁶ ≡ 1 (mod 7) and 100 = 6 · 16 + 4, so 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).

How do the theorems give inverses?

From a^(p−1) ≡ 1, the inverse of a mod p is a^(p−2).

What to learn next