Fermat's little theorem

Statement

For a relatively prime number

Suppose is a prime number and is a natural number that is not a multiple of . Then, the following equivalent statements hold:

1. (Divisibility form): divides .
2. (Congruence form): .
3. (Order of element modulo another): The order of modulo divides .

For a not necessarily relatively prime number

Suppose is a prime number and is a natural number, not necessarily relatively prime to . Then, the following equivalent statements hold:

1. (Divisibility form): divides .
2. (Congruence form): .

Related facts

Stronger facts

• Euler's theorem: This is a general version which states that if and are relatively prime, then where is the Euler phi-function of , i.e., the number of natural numbers less than or equal to that are relatively prime to . The Euler ph-i-function of a prime is , so this is a generalization.
• Order of element divides order of group: In a finite group, the order of any element divides the order of the group. This is a corollary of Lagrange's theorem in group theory. Fermat's little theorem is a special case of this where the group is the multiplicative group modulo , which has order .
• Primitive roots exist modulo primes: For any prime , there exists a natural number relatively prime to such that is precisely equal to the order of mod : in other words, no smaller power of is modulo . Such an is termed a primitive root. This follows from the fact that the multiplicative group of a prime field is cyclic, which in turn follows from the more general fact that multiplicative group of a field implies every finite subgroup is cyclic.

Other related facts

• Wilson's theorem: This states that for any prime , .
• For a given modulo that is relatively prime to , is modulo if and only if is a quadratic residue modulo .
• Period in decimal expansion of reciprocal of prime divides prime minus one: Suppose is chosen as a base for writing numbers, and is a prime that does not divide . Then, the expansion of in base has period dividing . In fact, the period equals the order of modulo , and it divides by Fermat's little theorem. It equals if and only if is a primitive root modulo . For , such primes are termed full reptend primes.

Converse

If, for a given relatively prime to , divides , it does not follow that is prime. This leads to some terminology:

• Fermat pseudoprime to base is a composite number such that and are relatively prime and divides . (Caution: Fermat prime means something very different!)
• Poulet number is a Fermat pseudoprime to base .
• Carmichael number, also called absolute pseudoprime, is a composite natural number such that divides for all relatively prime to . Equivalently, divides for all .