# Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime [Wilson's Theorem]

How can I show that $(n-1)!$ is congruent to $-1 \pmod{n}$ if and only if $n$ is prime?

Thanks.

## 5 Answers

$$n\text{ is prime if }(n-1)! \equiv -1 \pmod n$$

This direction is easy. If $n$ is composite, then there exists $k|n$ and $k\lt n$. So $k|(n-1)!$ and $k \equiv 1 \pmod n$. This means $k$ needs to divide $1$. So $n$ must be prime (or $1$, but we can eliminate this by substitution).

$$(n-1)! \equiv -1\text{ if }n\text{ is prime}$$

Wikipedia contains two proofs of this result known as Wilson's theorem. The first proof only uses basic abstract algebra and so should be understandable with a good knowledge of modular arithmetic. Just in case, I prove below that each element $1, 2, ... n-1$ has a unique inverse $\mod n$.

They use the fact that integers $\mod p$ form a group and hence that each element $x$ not congruent $0$ has a multiplicative inverse (a number $y$ such that $xy \equiv 1 \mod n$. We show this as follows. Suppose $n \nmid x$, for $n$ prime. From the uniqueness of prime factorisations, $xn$ is the first product of $x$, after $0x$, divisible by $n$ (use prime factorisation theorem). If we look at the series $kn \mod n$, this cycles and must have cycle length $n$. Therefore, each element $x, 2x,... nx$ must be different modulo $n$, including one, $y$, with $xy \equiv 1 \mod n$. Furthermore, due to the cycle length being $n$, each only one of those elements will be an inverse. So every element has a unique inverse (although 1 and -1 are their own inverses).

• I was satisfied with just the name of the theorem. Adding the proof certainly justifies an upvote. – Tomer Vromen Jul 21 '10 at 15:16

Hint $\rm\ (p\!-\!1)!\bmod p\,$ is the product of all elts of $\rm\, {\mathbb F}_p^*.\,$ The map $\rm n \mapsto n^{-1}$ is a permutation of $\rm\:{\mathbb F}_p^*\:$ of order $2$ so it decomposes into cycles of length $1$ or $2,$ which partition the product. Each $2$-cycle $\rm (n, n^{-1})$ has product $1$ so is deletable, leaving only the product of $1$-cycles $\rm (n)$. They satisfy $\rm\: n^{-1} = n \Rightarrow n^2 = 1 \Rightarrow n = \color{#0a0}{- 1}\,$ or $\color{#c00}1,\,$ by $\rm{\mathbb F}_p$ a field. So the product reduces to $\,\color{#0a0}{-1}\cdot\color{#c00}1 = -1$.

This generalizes: if a finite abelian group has a unique element of order $2$ then it is equal to the product of all the elements; otherwise the product is $1$, e.g. see this thread for hints (this is sometimes called the group-theoretic form of Wilson's Theorem).

Notice how we've exploited the existence of a symmetry - here an involution that induces a natural pairing of elts. Frequently involution and reflection symmetries lie at the heart of elegant proofs, e.g. see the elegant proof by Liouville, Heath-Brown and Zagier, that every prime $\equiv 1 \pmod 4$ is a sum of $2$ squares, or the little-known beautiful reflective generation of the ternary tree of primitive Pythagorean triples due to Aubry.

Here are a couple possible proofs of Wilson's theorem for $p>2$ ($p=2$ is easily checked):

1. We have that $x^{p-1}-1$ has roots $1,2,\ldots,p-1$ over $\mathbb{Z}/p\mathbb{Z}$ (by Fermat's Little Theorem). But as $\mathbb{Z}/p\mathbb{Z}$ is a field, we have unique factorization of polynomials, so that $x^{p-1}-1=(x-1)(x-2)\ldots(x-(p-1))$. Comparing constant terms wields Wilson's theorem.

2. Let $g$ be a primitive root modulo $p$. Then $(p-1)!\equiv g\times g^2\times \ldots \times g^{p-1}=g^{p\frac{p-1}{2}}\equiv g^{\frac{p-1}{2}}\bmod{p}$ by Fermat's Little Theorem, and $g^{\frac{p-1}{2}}\equiv -1 \bmod{p}$ because if $(g^{\frac{p-1}{2}})^2=g^{p-1}\equiv 1 \bmod{p}$ and $g^{\frac{p-1}{2}}\not \equiv 1 \bmod{p}$ by the definition of primitive root.

[NOTE: it seems that there is some difference between preview and actual output, so instead if using (mod p) I stick with (p)]

to show that $(p-1)! \equiv -1 (p)$ without explicitly use group theory, maybe the simplest path is: (the following assumes $p$ is odd, but if $p=2$ then the result is immediate)

1. given $n \ne 0$, all values $n, 2n, ... (p-1)$ $n$ are different mod $p$. Otherwise, if $hn \equiv kn (p)$ then $(h-k)n \equiv 0 (p)$ against the hypothesis that $p$ is prime.

2. this means that each $n$ has an inverse mod $p$, that is for each $n$ there is a $m$ such that $mn \equiv 1 (p)$.

3. the equation $x^2\equiv 1 (p)$ may be written as $(x+1)(x-1) \equiv 0 (p)$; therefore its only solutions are $x \equiv 1 (p)$ and $x \equiv -1 (p)$. For each other number $n$, an inverse $m$ must exist (because of the pigeonhole principle) but $m \neq n$.

4. we are nearly done. Let's couple every number from $2$ to $p-2$ with its own inverse. Their product is $1 (p)$, so they don't count in the overall total. $1$ does not count either; it remains just $p-1$, that is $-1 (p)$ as requested.

• For 2., it is vital that the inverse is unique. Otherwise, this is a very nice summary – Casebash Jul 21 '10 at 13:16
• if the inverse were not unique, we would have h and k such that nh &equiv; 1 and nk &equiv; 1, and we fall again in case 1. – mau Jul 21 '10 at 18:44
• Beautiful proof! Well explained! – Björn Lindqvist Dec 24 '18 at 2:15

Proof:
Let p be an odd prime number.
Consider the group $U_p=${equivalent classes of $a$|$p>a>0$, $gcd(a,p)=1$}
(equivalent relation:$a\equiv b \pmod p$, binary operation:[a][b]=[ab]).
p is a prime,so $U_p=${[a]|$1\leq a\leq p-1$}.
Since $U_p$ is a finite abelian group, $(\prod_{1}^{p-1}[a])^2=\prod_{1}^{p-1}[a]*\prod_{1}^{p-1}[a^{-1}]=$,
so $[(p-1)!]^2\equiv 1 \pmod p$,
therefore, either $(p-1)!\equiv 1\pmod p$$(!)$ or $(p-1)!\equiv -1 \pmod p(!!)$.
Now we'll show that the first statement (!) is incorrect, thus forcing the second statement to be true.
Consider $[p-1]$, we know that $o([p-1])=2$, because:
First we know that $p|p(p-2)$,
or $p|[(p-1)+1][(p-1)-1]$,
or $p|[(p-1)^2-1]$,
so $(p-1)^2\equiv 1\pmod p$,
or $[(p-1)^2]=$,
or$[p-1]^2=$.
Assume that there exists an element $[a],2\leq a \leq p-2$, such that $[a]^2=$,
therefore $a^2\equiv 1\pmod p$,
or $p|(a-1)(a+1)$,
so $p|(a-1)$ and/or $p|(a+1).$ But $1\leq a-1 \leq p-3$,
therefore p doesn't divide $a-1$, similarly, $p$ doesn't divide $a+1$. So the assumption is incorrect, in other words, only  and [p-1] are self-paired.
Therefore, consider the product: $x=...[p-1]$,
Apart from $$ and $[p-1]$, all other elements are paired together with their inverses,
so $x=[(p-1)!]=[p-1]\neq $,
or $[(p-1)!]\neq $.
So it is false that $(p-1)!\equiv 1\pmod p$.
This forces (!!)to be true,so it must be true that $(p-1)!\equiv -1\pmod p$.
This completes the proof.