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.[1] It is called “little” only in deference to Fermat’s last theorem, and some authors in fact call it just Fermat’s theorem.[2]

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
,[3] 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.[4]

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.

• Chinese hypothesis
• A000790: Primary pretenders: least composite  c
such that  n c   ≡   n  (mod c)
.

## Notes

1. Schroeder (2009), p. 139.
2. Such as Manfred R. Schroeder.
3. Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007) p. 16, Theorems 9.6 and 9.7.
4. R. Crandall and C. Pomerance. Prime Numbers: A Computational Perspective New York: Springer-Verlag (2001): p. 121.

## References

• Manfred R. Schroeder, Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing and Self-Similarity, 5th Ed. Springer (2009).