This site is supported by donations to The OEIS Foundation.

# Fermat's little theorem

Fermat’s little theorem has big consequences in number theory and its applications, such as data encryption. It is called “little” only in deference to Fermat’s last theorem, and some authors in fact call it just Fermat’s theorem.

Theorem. (Pierre de Fermat)

Given a prime number
 p
and an integer
 b
coprime to
 p
,
 b  p  − 1   ≡   1  (mod p)
.

Proof. Consider the
 p  −  1
numbers
 b, 2 b, 3 b, ..., (  p  −  1) b
. Those are all different and nonzero
 (mod p)
, since
 p
is prime and
 b
is coprime to
 p
. Indeed, if
 u b   ≡   v b  (mod p)
, then
 u   ≡   v  (mod p)
, since we can “cancel the
 b
” (
 b
being coprime to
 p
). So we have
 p  −  1
numbers, all different, and none of them is 0
 (mod p)
. So they must be congruent to
 1, 2, 3, ..., p  −  1
in some order. Multiplying them together, we get
 P = (  p  −  1)! b  p  − 1
. So their product is congruent to
 (  p  −  1)!  (mod p)
. We now have two expressions for this product, so we can equate them:
 (  p  −  1)! b  p  − 1   ≡   (  p  −  1)!  (mod p).
Now
 (  p  −  1)!
is coprime to
 p
, so we can again cancel, to give
 b  p  − 1   ≡   1  (mod p)

For example, 10 12 is 1 more than 999999999999, which is divisible by 13 (as it is 76923076923  ×  13).

Fermat’s little theorem is a special case of Euler’s theorem that
 b   ≡   1  (mod n)
if
 gcd (b, n) = 1
, since
 ϕ (  p) = p  −  1
and
 gcd (b, p) = 1
for any
 b
not a multiple of
 p
.
The theorem is best demonstrated with small odd primes, such as 3 and 5. In the case of
 p = 3
, the theorem tells us that no square is one less than a multiple of 3. If we take integers that are not multiples of 3, i.e {1, 2, 4, 5, 7, 8, 10, 11, ...}, square them {1, 4, 16, 25, 49, 64, 100, 121, ...}, and subtract 1 from each, we get multiples of 3 {0, 3, 15, 24, 48, 63, 99, 120, ...} But it also holds for
 p = 2
, though giving as it does the uninteresting result that an odd number is not even number.

## Fermat pseudoprimes

However, the theorem can’t be used as a proof of primality for
 n
, at least not if we only test for one base
 b
coprime to
 n
. There are composite numbers
 n
for which the congruence
 b n  − 1   ≡   1  (mod n)
holds for some bases
 b
coprime to
 n
.

For example, for the composite number 341 = 11  ×  31, we have

2 340  =  2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776,

which leaves a remainder of 1 when divided by 341. However,

3 340  =  1664280806589814803858571371708626691451909331385734291010900950997276297957762658553727546535190828834204613885667545045874010453464713005017905547836267732294801,
and that leaves a remainder of 56 when divided by 341. These numbers are called Fermat pseudoprimes to a given base
 b
(the Fermat pseudoprimes to base 2 are also called Poulet numbers). Though there are infinitely many such pseudoprimes, they “are sparsely distributed,” enabling the theorem to be used as a reasonable step in primality testing.

In the case of 341, we can see that among small bases, remainders other than 1 are given often enough, e.g.

A206786 Remainder of
 n 340
divided by 341.
{1, 1, 56, 1, 67, 56, 56, 1, 67, 67, 253, 56, 67, 56, 1, 1, 56, 67, 56, 67, 67, 253, 1, 56, 56, 67, 1, 56, 1, 1, 155, 1, 187, 56, 1, 67, 56, 56, 1, 67, 67, 67, 56, 253, 56, 1, 1, 56, 67, 56, 67, 67, 67, 1, 242, ...}

### Absolute Fermat pseudoprimes

So, what about testing for all bases
 b
coprime to
 n
? Unfortunately, some composite numbers are pseudoprimes to all bases
 b
coprime to
 n
, these are called Carmichael numbers (or absolute Fermat pseudoprimes), the first such number being 561 = 3  ×  11  ×  17.