Fermat's little theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For other theorems named after Pierre de Fermat, see Fermat's theorem.

Fermat's little theorem states that if p is a prime number, then for any integer a, the number a pa is an integer multiple of p. In the notation of modular arithmetic, this is expressed as




For example, if a = 2 and p = 7 then 26 = 64 and 64 − 1 = 63 is thus a multiple of 7.



Pierre de Fermat


If p is a prime and a is any integer not divisible by p, then a p - 1 - 1 is divisible by p.

In fact, the original statement was

Tout nombre premier mesure infailliblement une des puissances – 1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné – 1 ; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.

This may be translated in modern terminology, with explanations and formulas inserted between brackets, for easier understanding:

Every prime number [p] divides necessarily one of the powers –1 of any [geometric] progression [a, a2, a3, ...] [that is there exists t such that p divides at – 1], and the exponent of this power [t] divides the given prime –1 [divides p – 1]; and, after one has found the first power [t] that satisfies the question, all those whose exponents are multiple of the exponent of the first one satisfy similarly the question [that is, all multiples of the first t have the same property].





The term "Fermat's Little Theorem" was probably first used in print in 1913 in Zahlentheorie by Kurt Hensel:




Further history[edit]

Main article: Chinese hypothesis

Some mathematicians independently made the related hypothesis (sometimes incorrectly called the Chinese Hypothesis) that 2p ≡ 2 (mod p) if and only if p is a prime. Indeed, the "if" part is true, and is a special case of Fermat's little theorem. However, the "only if" part of this hypothesis is false: for example, 2341 ≡ 2 (mod 341), but 341 = 11 × 31 is a pseudoprime. See below.




Fermat's little theorem is a special case of Euler's theorem: for any modulus n and any integer a coprime to n, we have

where φ(n) denotes Euler's totient function (which counts the integers between 1 and n that are coprime to n). Euler's theorem is indeed a generalization, because if n = p is a prime number, then φ(p) = p − 1.

A slight generalization of Euler's theorem, which immediately follows from it, is: if a, n, x, y are integers with n positive and a and n coprime, then

If , then .

This follows as x is of the form y + φ(n)k, so

In this form, the theorem finds many uses in cryptography and, in particular, underlies the computations used in the RSA public key encryption method.[7] The special case with n a prime may be considered a consequence of Fermat's little theorem.


The algebraic setting of Fermat's little theorem can be generalized to finite fields.



If there exists an a such that

and for all primes q dividing p − 1

then p is prime.



If a and p are coprime numbers such that a p − 1 − 1 is divisible by p, then p need not be prime. If it is not, then p is called a pseudoprime to base a (or a Fermat pseudoprime). F. Sarrus in 1820 found 341 = 11 × 31 as one of the first pseudoprimes, to base 2.[8]


is either a prime or a Carmichael number.

Miller–Rabin primality test[edit]


If p is an odd prime number, and p – 1 = 2s d, with d odd, then for every a prime to p, either ad ≡ 1 mod p, or there exists t such that 0 ≤ t < s and a2td ≡ −1 mod p


Miller–Rabin test uses this property in the following way. Given p = 2s d + 1, with d odd, an odd integer for which primality has to be tested, choose randomly a such that 1 < a < p; then compute b = ad mod p; if b is not 1 nor −1, then square it repeatedly modulo p until getting 1, −1, or having squared d times. If b ≠ 1 and −1 has not been obtained, then p is not prime. Otherwise, p may be prime or not. If p is not prime, the probability that this is proved by the test is higher than 1/4. Therefore, after k non-conclusive random tests, the probability that p is not prime is lower than (3/4)k, and may thus be made as low as desired, by increasing k.


See also[edit]


  1. ^ Long 1972, pp. 87–88
  3. ^ a b c Burton 2011, p. 514
  4. ^ Fermat, Pierre (1894), Tannery, P.; Henry, C., eds., Oeuvres de Fermat. Tome 2: Correspondance, Paris: Gauthier-Villars, pp. 206–212  (in French)
  6. ^ Ore 1988, p. 273
  7. ^ Trappe, Wade; Washington, Lawrence C. (2002), Introduction to Cryptography with Coding Theory, Prentice-Hall, p. 78, ISBN 0-13-061814-4 
  8. ^ https://oeis.org/A128311



Further reading[edit]

External links[edit]