= Fermat little theorem
{c}
{title2=$a^{p-1}\equiv1\pmod p$}
{wiki=Fermat's_little_theorem}
= Fermat's little theorem
{c}
{synonym}
For a <prime number> $p$ and an <integer> $a$ not divisible by $p$, <Fermat's little theorem> states the <modular congruence>
$$
a^{p-1}\equiv1\pmod p\qquad(p\nmid a).
$$
Equivalently, for every <integer> $a$, including $a<0$ and multiples of $p$,
$$
a^p\equiv a\pmod p.
$$
The first formulation follows from the second by multiplying by a <modular multiplicative inverse> of $a$. Conversely, multiply the first by $a$ when $p\nmid a$; when $p\mid a$, both sides of the second are zero modulo $p$. The <divisibility> condition in the first formulation is essential.<Euler’s Theorem by Keith Conrad>[p. 1, Theorem 1.1 and the equivalence of nonzero and coprime classes for a prime modulus]{ref}
For $p=7$, $3^6=729=7\cdot104+1$, so $3^6\equiv1\pmod7$ and $3^7\equiv3\pmod7$. Also $(-2)^6=64\equiv1\pmod7$, while $7^6\equiv0\pmod7$: a zero <residue class> cannot satisfy the first formulation. It does satisfy $7^7\equiv7\equiv0\pmod7$. A failure at a zero <residue class> therefore says nothing against a candidate's being a <prime number>.
The <prime number> $p=2$ is included. Its only nonzero <residue class> is one: every odd <integer> $a$ satisfies $a^{2-1}=a\equiv1\pmod2$. Every <integer> also satisfies $a^2\equiv a\pmod2$, because $a(a-1)$ is even. Testing the first formulation with an even <integer> would violate its hypothesis.
The useful surprise is that every nonzero <residue class> returns to one at the same <exponent> $p-1$, although its shortest return can be earlier. This gives <exponent reduction for units>: for a <nonnegative integer> $k$, $a^k\equiv a^{k\bmod(p-1)}\pmod p$ when $p\nmid a$. It also computes a <modular multiplicative inverse> as $a^{p-2}$ modulo $p$, including $p=2$. <Repeated squaring> makes these <modular exponentiations> practical.
In <group theory>, the nonzero <residue classes> form the <multiplicative group of integers modulo n> with $n=p$, of <group order> $p-1$. <Lagrange's theorem> says that the <multiplicative order> of $a$ divides $p-1$, giving the guaranteed return. <Euler's theorem> extends this to a general <integer modulus> $n$, using the <units> and <Euler's totient function> $\varphi(n)$; the <Carmichael function> gives the least common return <exponent> for all <units>. A nonzero <residue class> modulo a <composite number> need not be a <unit>.
<Leonhard Euler>'s paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with <exponent> $n-1$ leave zero or one upon division by a <prime number> $n$. The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.<Observations on a certain theorem of Fermat and on others concerning prime numbers by Leonhard Euler>[English translation, p. 1 publication note; p. 2 paragraph before footnote 3; p. 3, Theorem 1]{ref}
Back to article page
