This site is supported by donations to The OEIS Foundation.

Fermat's little theorem

From OeisWiki
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


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
,
bp  − 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
ub   ≡   vb  (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)! bp  − 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)! bp  − 1   ≡   (  p  −  1)!  (mod p).
Now
(  p  −  1)!
is coprime to
p
, so we can again cancel, to give
bp  − 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ϕ (n)   ≡   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
bn  − 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.

See also

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).

External links