Fermat's Little Theorem Explained with Worked Examples

If is prime and , then . Equivalently, for every integer .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Fermat's little theorem means

Check: , so . The exponent can be reduced modulo : to find , write , so . For a larger prime, , since . This makes huge powers easy by hand; the arithmetic of remainders is explained in remainders.

The proof multiplies the residues , which are a rearrangement of modulo , so ; cancelling (invertible, see Wilson's theorem) gives the result. Another proof expands with the binomial theorem, since is divisible by for (binomial coefficients).

The generalisation to composite moduli is Euler's theorem. Fermat gives inverses, , used with linear congruences, a quick (but imperfect) primality test, and the encryption in RSA; its relative for squares is Euler's criterion.

What is it used for?

Fermat's theorem says that powers of a number cycle back to 1 modulo a prime, which makes huge powers easy to reduce.

How to use fermat's little theorem

  1. Check that is prime and .
  2. Reduce the exponent modulo .
  3. Compute the remaining small power modulo .
  4. Verify with direct computation for small cases.

Graph

Powers 3ⁿ mod 7 repeat with period 6, returning to 13⁶ ≡ 13¹² ≡ 102468101201234567Powers 3ⁿ mod 7 repeat with period 6, returning to 1n3ⁿ mod 7Graph with x from 0 to 13 and y from 0 to 7.5. Shows 3ⁿ mod 7 (13); point 3⁶ ≡ 1 at (6, 1); point 3¹² ≡ 1 at (12, 1).

The cycle length 6 divides p − 1 = 6.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: 3⁶ mod 7

Verify Fermat for , .

Worked example
Answer
729≡1(mod7)729\equiv1\pmod7
  1. 3⁶

Example 2: 2¹⁰⁰ mod 101

Find .

Worked example
Answer
11
  1. p − 1

Example 3: 3²⁰⁰ mod 7

Find .

Worked example
Answer
22
  1. 200
  2. Result

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

3⁶ mod 7

aᵖ⁻¹ ≡ 1

1.

2¹⁰⁰ mod 7

100 mod 6 = 4, so 2⁴ mod 7

2.

Inverse of 3 mod 7

3⁵ mod 7

5.

5¹² mod 13

aᵖ⁻¹ ≡ 1

1.

Word problems

If p is prime and p ∤ a then aᵖ⁻¹ ≡ 1 (mod p); equivalently aᵖ ≡ a. It reduces large exponents and gives inverses a⁻¹ ≡ aᵖ⁻².

Direct

Find 3⁶ mod 7.

  1. 729 = 104·7 + 1
  2. Check: ✓1

Large exponent

Find 2¹⁰⁰ mod 7 using exponent mod 6.

  1. 100 mod 6 = 4
  2. 2⁴ mod 7 = 2
  3. Check: ✓2

Inverse Higher

Find 3⁻¹ mod 7 as 3⁵ mod 7.

  1. 243 mod 7
  2. Check: 5 (3·5 = 15 ≡ 1) ✓5

Another prime Higher

Find 5¹² mod 13.

  1. aᵖ⁻¹
  2. Check: ✓1

Common mistakes

Non-prime modulus

applies to 9 ✗

needs prime p ✓

Use Euler instead.

Multiple of p

a = 7 ✗

p ∤ a ✓

Then aᵖ ≡ 0.

Exponent mod p

reduce by 7 ✗

reduce by p − 1 ✓

Period p − 1.

Forgetting the −1

aᵖ ≡ 1 ✗

aᵖ⁻¹ ≡ 1 ✓

Check.

Exam tips

  1. aᵖ⁻¹ ≡ 1.
  2. Reduce exponents mod p − 1.
  3. Inverse: aᵖ⁻².
  4. Prime modulus only.
  5. p ∤ a.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. 2⁶ mod 7 Foundation

1

2. 3¹⁰ mod 11 Foundation

1

3. 2¹⁰ mod 11 Foundation

1

4. 4¹² mod 13 Higher

1

5. 3²⁰ mod 7 (20 mod 6 = 2) Higher

2

6. Inverse of 2 mod 11: 2⁹ mod 11 Higher

6

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Fermat’s little theorem
aᵖ⁻¹ ≡ 1 (mod p).
Prime (p)
Modulus.
Modular inverse
aᵖ⁻².
Exponent reduction
Mod p − 1.
Euler’s theorem
General modulus.
Pseudoprime
Composite passing the test.

Frequently asked questions

What is Fermat’s little theorem?

aᵖ⁻¹ ≡ 1 (mod p) for prime p not dividing a.

How do I reduce large powers?

Reduce the exponent modulo p − 1.

How do I find an inverse?

a⁻¹ ≡ aᵖ⁻².

Does it work for composite moduli?

No; use Euler’s theorem.

Which page covers Euler’s theorem?

Euler’s theorem and the totient.

Which page covers Wilson’s theorem?

Wilson’s theorem.

More in Discrete maths and number theory and the formula sheets.