If is a prime number and is a natural number, then
(1)

Furthermore, if ( does not divide ), then there exists some smallest exponent such that
(2)

and divides . Hence,
(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 . Suppose (i.e., divides ). Then examine
(4)

From the binomial theorem,
(5)

Rewriting,
(6)

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

as assumed, so the hypothesis is true for any . 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 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. 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 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 table of the smallest pseudoprimes for the first 100 bases follows (OEIS A007535; Beiler 1966, p. 42 with typos corrected).
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  112  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  45  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  247  97  105 
18  25  38  39  58  133  78  341  98  99 
19  45  39  95  59  87  79  91  99  145 
20  21  40  91  60  341  80  81  100  153 
21  55  41  105  61  91  81  85 