# 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

### 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 .