![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
If is a Prime number and
a Natural Number, then
![]() |
(1) |
![]() |
(2) |
![]() |
(3) |
The theorem is easily proved using mathematical Induction. Suppose . Then examine
![]() |
(4) |
![]() |
(5) |
![]() |
(6) |
![]() |
(7) |
Fermat's little theorem shows that, if is Prime, there does not exist a base
with
such that
possesses a nonzero residue modulo
. If such base
exists,
is therefore guaranteed to be composite.
However, the lack of a nonzero residue in Fermat's little theorem does not guarantee that
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. Composite Numbers known as
Fermat Pseudoprimes (or sometimes simply ``Pseudoprimes'') have zero
residue for some
s 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
Relatively Prime to
. However, Fermat's Little Theorem Converse provides a criterion for certifying the
primality of a number.
A number satisfying Fermat's little theorem for some nontrivial base and which is not known to be composite is called a
Probable Prime. A table of the smallest Pseudoprimes for the first 100 bases
follows
(Sloane's A007535).
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
2 | 341 | 22 | 69 | 42 | 205 | 62 | 63 | 82 | 91 |
3 | 91 | 23 | 33 | 43 | 77 | 63 | 341 | 83 | 105 |
4 | 15 | 24 | 25 | 44 | 45 | 64 | 65 | 84 | 85 |
5 | 124 | 25 | 28 | 45 | 76 | 65 | 133 | 85 | 129 |
6 | 35 | 26 | 27 | 46 | 133 | 66 | 91 | 86 | 87 |
7 | 25 | 27 | 65 | 47 | 65 | 67 | 85 | 87 | 91 |
8 | 9 | 28 | 87 | 48 | 49 | 68 | 69 | 88 | 91 |
9 | 28 | 29 | 35 | 49 | 66 | 69 | 85 | 89 | 99 |
10 | 33 | 30 | 49 | 50 | 51 | 70 | 169 | 90 | 91 |
11 | 15 | 31 | 49 | 51 | 65 | 71 | 105 | 91 | 115 |
12 | 65 | 32 | 33 | 52 | 85 | 72 | 85 | 92 | 93 |
13 | 21 | 33 | 85 | 53 | 65 | 73 | 111 | 93 | 301 |
14 | 15 | 34 | 35 | 54 | 55 | 74 | 75 | 94 | 95 |
15 | 341 | 35 | 51 | 55 | 63 | 75 | 91 | 95 | 141 |
16 | 51 | 36 | 91 | 56 | 57 | 76 | 77 | 96 | 133 |
17 | 45 | 37 | 45 | 57 | 65 | 77 | 95 | 97 | 105 |
18 | 25 | 38 | 39 | 58 | 95 | 78 | 341 | 98 | 99 |
19 | 45 | 39 | 95 | 59 | 87 | 79 | 91 | 99 | 145 |
20 | 21 | 40 | 91 | 60 | 341 | 80 | 81 | 100 | 259 |
21 | 55 | 41 | 105 | 61 | 91 | 81 | 85 |
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
References
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 61, 1987.
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.
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 ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.
![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
© 1996-9 Eric W. Weisstein