TOPICS
Search

Fermat's Little Theorem


If p is a prime number and a is a natural number, then

 a^p=a (mod p).
(1)

Furthermore, if pa (p does not divide a), then there exists some smallest exponent d such that

 a^d-1=0 (mod p)
(2)

and d divides p-1. Hence,

 a^(p-1)-1=0 (mod p).
(3)

The theorem is sometimes also simply known as "Fermat's theorem" (Hardy and Wright 1979, p. 63).

This is a generalization of the Chinese hypothesis and a special case of Euler's totient theorem. It is sometimes called Fermat's primality test and is a necessary but not sufficient test for primality. Although it was presumably proved (but suppressed) by Fermat, the first proof was published by Euler in 1749. It is unclear when the term "Fermat's little theorem" was first used to describe the theorem, but it was used in a German textbook by Hensel (1913) and appears in Mac Lane (1940) and Kaplansky (1945).

The theorem is easily proved using mathematical induction on a. Suppose p|a^p-a (i.e., p divides a^p-a). Then examine

 (a+1)^p-(a+1).
(4)

From the binomial theorem,

 (a+1)^p=a^p+(p; 1)a^(p-1)+(p; 2)a^(p-2)+...+(p; p-1)a+1.
(5)

Rewriting,

 (a+1)^p-a^p-1=(p; 1)a^(p-1)+(p; 2)a^(p-2)+...+(p; p-1)a.
(6)

But p divides the right side, so it also divides the left side. Combining with the induction hypothesis gives that p divides the sum

 [(a+1)^p-a^p-1]+(a^p-a)=(a+1)^p-(a+1),
(7)

as assumed, so the hypothesis is true for any a. The theorem is sometimes called Fermat's simple theorem. Wilson's theorem follows as a corollary of Fermat's little theorem.

Fermat's little theorem shows that, if p is prime, there does not exist a base a<p with (a,p)=1 such that a^(p-1)-1 possesses a nonzero residue modulo p. If such base a exists, p is therefore guaranteed to be composite. However, the lack of a nonzero residue in Fermat's little theorem does not guarantee that p is prime. The property of unambiguously certifying composite numbers while passing some primes make Fermat's little theorem a compositeness test which is sometimes called the Fermat compositeness test. A number satisfying Fermat's little theorem for some nontrivial base and which is not known to be composite is called a probable prime.

Composite numbers known as Fermat pseudoprimes (or sometimes simply "pseudoprimes") have zero residue for some as and so are not identified as composite. Worse still, there exist numbers known as Carmichael numbers (the smallest of which is 561) which give zero residue for any choice of the base a relatively prime to p. However, Fermat's little theorem converse provides a criterion for certifying the primality of a number. A table of the smallest pseudoprimes P for the first 100 bases a follows (OEIS A007535; Beiler 1966, p. 42 with typos corrected).

aPaPaPaPaP
234122694220562638291
391233343776334183105
4152425444564658485
5124252845766511285129
63526274613366918687
7252765476567858791
892845484968698891
9282935496669858999
103330495051701699091
1115314951657110591115
12653233528572859293
1321338553657311193301
14153435545574759495
1534135515563759195141
165136915657767796133
1745374557657724797105
1825383958133783419899
194539955987799199145
20214091603418081100153
21554110561918185

See also

Binomial Theorem, Carmichael Number, Chinese Hypothesis, Composite Number, Compositeness Test, Euler's Theorem, Fermat's Little Theorem Converse, Fermat Pseudoprime, Modulo Multiplication Group, Pratt Certificate, Primality Test, Prime Number, Pseudoprime, Relatively Prime, Totient Function, Wieferich Prime, Wilson's Theorem, Witness

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 61, 1987.Beiler, A. H. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 141-142, 1996.Courant, R. and Robbins, H. "Fermat's Theorem." §2.2 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 37-38, 1996.Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, pp. 118-125, 2000.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Hensel, K. Zahlentheorie. Berlin: G. J. Göschen, 1913.Kaplansky, I. "Lucas's Tests for Mersenne Numbers." Amer. Math. Monthly 52, 188-190, 1945.Mac Lane, S. "Modular Fields." Amer. Math. Monthly 47, 259-274, 1940.Nagell, T. "Fermat's Theorem and Its Generalization by Euler." §21 in Introduction to Number Theory. New York: Wiley, pp. 71-73, 1951.Séroul, R. "The Theorems of Fermat and Euler." §2.8 in Programming for Mathematicians. Berlin: Springer-Verlag, p. 15, 2000.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 20, 1993.Sloane, N. J. A. Sequence A007535/M5440 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Fermat's Little Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FermatsLittleTheorem.html

Subject classifications