= Wilson's theorem
{c}
{title2=$(n-1)!\equiv-1\pmod n$}
{wiki}
= Wilson theorem
{c}
{synonym}
For an <integer> $n>1$, <Wilson's theorem> characterizes <prime numbers> by a <factorial>:
$$
n\text{ is prime}\quad\Longleftrightarrow\quad(n-1)!\equiv-1\pmod n.
$$
The right side is an <integer congruence>, so the least nonnegative <remainder> is $n-1$. For example, $4!=24\equiv4\pmod5$ certifies that five is a <prime number>, whereas $5!=120\equiv0\pmod6$ rules out six. <Wilson's Theorem and Fermat's Theorem by Bruce Ikenaga>{ref}
\Image[/wilson-factorial-residue-primality.png]
{title=Factorial residues distinguish primes from composites, with inverse pairs explaining the prime case}
For an odd <prime number> $p$, each nonzero <congruence class> has a unique <modular multiplicative inverse>. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when $a^2\equiv1\pmod p$; since $p\mid(a-1)(a+1)$, <Euclid's lemma> leaves only $a\equiv\pm1$. Their product is $-1$. The <prime number> two needs a separate check: $1!\equiv-1\pmod2$. Conversely, a proper <divisor> $1<d<n$ divides both $n$ and $(n-1)!$, so the displayed <integer congruence> would force $d\mid1$, a contradiction. <Wilson's Theorem and Fermat's Theorem by Bruce Ikenaga>{ref}
The <composite numbers> have an even sharper pattern: $(n-1)!\equiv0\pmod n$ for every <composite number> $n>4$, but $3!=6\equiv2\pmod4$. To check the zero claim, write $n=ab$ with $1<a\leq b<n$. If $a<b$, both occur as different factors in the <factorial>. If $a=b\geq3$, the different factors $a$ and $2a$ both occur since $2a<a^2=n$, and their product is divisible by $n$. The only excluded case is $a=b=2$. Thus four is an exception to the zero pattern, but still fails <Wilson's theorem>: its required <remainder> would be three.
This is an exact <primality testing> criterion, but direct evaluation is expensive: even reducing modulo $n$ after every multiplication still takes a number of multiplications proportional to $n$, which grows exponentially with the number of <binary digits> of $n$. The problem is not merely storing a huge <factorial>. The more useful role of <Wilson's theorem> is simplifying <factorial> expressions in <modular arithmetic>. For instance, if $p>2$ is a <prime number>, then $(p-1)(p-2)!\equiv-1\pmod p$ gives $(p-2)!\equiv1\pmod p$ by a <modular multiplicative inverse>.
Back to article page
