Theorem

Fermat's little theorem

Arithmetic • Number System • Divisibility

Formula

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

p

is a prime and

a

is an integer not divisible by

p

, then

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

How to use it

1Check both conditions first: the modulus must be prime, and the base must not be a multiple of it.
2When the exponent is exactly $p - 1$ the remainder is $1$ outright; when it is larger, write the exponent as $m (p - 1) + r$ and the power reduces to $a^{r} (mod p)$ .
3Use it to collapse an otherwise impossible power: $a^{p} \equiv a (mod p)$ follows by multiplying both sides by $a$ .

What is the remainder when

3^{16}

is divided by

17

Step-by-step

1
$17$ is prime and $17 ∤ 3$
Why: Both conditions of the theorem are met.
2
$3^{17 - 1} = 3^{16} \equiv 1 (mod 17)$
Why: The exponent is exactly $p - 1$ , so the theorem applies directly.

Answer

1

Watch out

The primality of

p

is essential:

2^{8} = 256 \equiv 4 (mod 9)

, not

1

, because

9

is not prime. The theorem also says nothing when

p ∣ a

, where the power is

\equiv 0

instead.

Builds on

Also known as

a^(p-1) = 1 mod p, remainder of a large power, little Fermat, power mod a prime