Fermat's little theorem

Statement

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

(Divisibility form): $p$ divides $a^{p - 1} - 1$ .
(Congruence form): $a^{p - 1} \equiv 1 (\mod p)$ .
(Order of element modulo another): The order of $a$ modulo $p$ divides $p - 1$ .

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

Euler's theorem: This is a general version which states that if $a$ and $n$ are relatively prime, then $a^{ϕ (n)} \equiv 1 mod n$ where $ϕ (n)$ is the Euler phi-function of $n$ , i.e., the number of natural numbers less than or equal to $n$ that are relatively prime to $n$ . The Euler ph-i-function of a prime $p$ is $p - 1$ , 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 $p$ , which has order $p - 1$ .
Primitive roots exist modulo primes: For any prime $p$ , there exists a natural number $a$ relatively prime to $p$ such that $p - 1$ is precisely equal to the order of $a$ mod $p$ : in other words, no smaller power of $a$ is $1$ modulo $p$ . Such an $a$ 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 Groupprops:Multiplicative group of a field implies every finite subgroup is cyclic.

Wilson's theorem: This states that for any prime $p$ , $(p - 1)! \equiv - 1 (\mod p)$ .
For a given $a$ modulo $p$ that is relatively prime to $p$ , $a^{(p - 1) / 2}$ is $1$ modulo $p$ if and only if $a$ is a quadratic residue modulo $p$ .
Period in decimal expansion of reciprocal of prime divides prime minus one: Suppose $b > 1$ is chosen as a base for writing numbers, and $p$ is a prime that does not divide $b$ . Then, the expansion of $1 / p$ in base $b$ has period dividing $p - 1$ . In fact, the period equals the order of $b$ modulo $p$ , and it divides $p - 1$ by Fermat's little theorem. It equals $p - 1$ if and only if $b$ is a primitive root modulo $p$ . For $b = 10$ , such primes $p$ are termed full reptend primes.

If, for a given $a$ relatively prime to $p$ , $p$ divides $a^{p - 1} - 1$ , it does not follow that $p$ is prime. This leads to some terminology:

Fermat pseudoprime to base $a$ is a composite number $n$ such that $a$ and $n$ are relatively prime and $n$ divides $a^{n - 1} - 1$ . (Caution: Fermat prime means something very different!)
Poulet number is a Fermat pseudoprime to base $2$ .
Carmichael number, also called absolute pseudoprime, is a composite natural number $n$ such that $n$ divides $a^{n - 1} - 1$ for all $a$ relatively prime to $n$ . Equivalently, $n$ divides $a^{n} - a$ for all $a$ .