Fermat's Little Theorem and Its Uses

In the Chinese book: 费马小定理及其应用

Mod a prime p, keep multiplying 1 by a: after p−1 steps you are back at 1.

📖 §2.3 of 《整除、同余与不定方程》M23 Guess, Then Prove line

Try this

$m = 7$ , $a = 3$ : go step by step, $1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1$ . It takes $6$ steps to get back to $1$ . Switch to $a = 2$ : how many steps? And $a = 6$ ?
Write down the number of steps for each of $a = 1, \dots, 6$ . How are they related to $6$ ?
The number of steps is always a divisor of $6$ , so after exactly $6$ steps you always land on $1$ . Look at the “Fermat test” row below.
Change $m$ to $11$ or $13$ . Is the Fermat test row all $1$ s?
Change $m$ to $9$ or $12$ : some values of $a$ never get back to $1$ at all. What shows up in that row?

Fermat's little theorem Let $p$ be a prime and $a$ an integer not divisible by $p$ . Then
$a^{p - 1} \equiv 1 (mod p)$
Multiply both sides by $a$ : $a^{p} \equiv a (mod p)$ , and this form holds for every integer $a$ .

Predict first

Mod $11$ , start at $1$ and keep multiplying by $a$ (where $a$ is not a multiple of $11$ ). The number of steps until you first get back to $1$ cannot be:

2

5

10

4

Choose an answer first; then you can see the result.

Why

The proof uses nothing but the picture from the previous stop: multiplying by $a$ is a reordering.

Multiply out both sides of the reordering

Step 1 / 6

The reordering
Mod $7$ , multiply by $3$ . $0$ stays put; $1, 2, \dots, 6$ are sent to $3, 6, 2, 5, 1, 4$ . These are the same six numbers, just in a different order.

$\equiv {3 \cdot 1, 3 \cdot 2, \dots, 3 \cdot 6} {1, 2, \dots, 6} (mod 7)$
Multiply each side together
Pull out the 3s
Cancel 6!
Check it on the powers picture
Use it to cut down exponents

Remove one condition

Break it

Counterexample lab: remove one condition

Conclusion: every $a$ not divisible by $p$ satisfies $a^{p - 1} \equiv 1 (mod p)$

$p = 13$ . All $12$ cells of the Fermat test are $1$ . Click different cells to change $a$ , then press “Finish”: the numbers of steps differ, but they are all divisors of $12$ .

Practice

Exercise 1Basic

Find the remainder when $5^{14}$ is divided by $13$ .

Exercise 2Basic

Find the remainder when $2^{2025}$ is divided by $11$ .

Exercise 3Advanced

Prove that for every integer $n$ , $n^{7} - n$ is divisible by $42$ .

Exercise 4Challenge

The prime $p$ satisfies $p ∣ (2^{p} + 1)$ . Find $p$ .

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Using Fermat's little theorem when the modulus is not prime

By Fermat's little theorem,

2^{14} \equiv 1 (mod 15)

What went wrong? Think first, then open

Diagnosis $15 = 3 \times 5$ is not prime, so the theorem says nothing about it. In fact $2^{4} = 16 \equiv 1 (mod 15)$ , so $2^{14} = (2^{4})^{3} \times 2^{2} \equiv 4$ .

Make sure the modulus is prime first. For a composite modulus, either find the period directly (here it is

4

) or split it into prime moduli and handle each one.

“Check the condition before using the theorem: is p prime?”

Exhibit

A base that is a multiple of p

1 4^{6} \equiv 1 (mod 7)

What went wrong? Think first, then open

Diagnosis $7 ∣ 14$ , so $1 4^{6} \equiv 0 (mod 7)$ . The theorem needs $p ∤ a$ : start from $1$ , multiply by $0$ , and once you fall into $0$ you never get out.

If you don't want to check this condition, use the other form:

a^{p} \equiv a (mod p)

, which holds for every integer

a

“a must not be a multiple of p”

Exhibit

Using the theorem backwards

2^{340} \equiv 1 (mod 341)

, so

341

is prime.

What went wrong? Think first, then open

Diagnosis $341 = 11 \times 31$ . It just happens that $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1$ , so $2^{340} \equiv 1$ . The theorem says “prime ⇒ remainder 1”, not “remainder 1 ⇒ prime”.

If the remainder is not

1

, you can be sure the number is composite; if it is

1

, you can conclude nothing. Try another base:

3^{340} \neq \equiv 1 (mod 341)

“The theorem only works in one direction”