Fermat's little theorem

Statement

For a relatively prime number

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:

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

For a not necessarily relatively prime number

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

1. (Divisibility form): $p$ divides $a^{p}-a$.
2. (Congruence form): $a^{p}\equiv a{\pmod {p}}$.

Related facts

Stronger facts

• Euler's theorem: This is a general version which states that if $a$ and $n$ are relatively prime, then $a^{\phi (n)}\equiv 1\mod n$ where $\phi (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 multiplicative group of a field implies every finite subgroup is cyclic.

Other related facts

• Wilson's theorem: This states that for any prime $p$, $(p-1)!\equiv -1{\pmod {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.

Converse

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