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

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

Thanks.

$$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. Jul 21, 2010 at 15:16

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

The converse is much easier:  if $$\,(n\!-\!1)!\equiv -1\pmod{\!n}\,$$ then $$\,n\,$$ is coprime to $$\,(n\!-\!1)!\,$$ and all its factors, which include all proper factors of $$\,n.\,$$ So the only proper factor of $$\,n\,$$ is $$\,1,\,$$ i.e. $$\,n\,$$ is prime. More generally see this answer.

Remark  See here for a generalization to the product of all the invertibles in $$\Bbb Z_n\! = \Bbb Z\bmod n.\,$$ Wilson's Theorem generalizes further: if a finite abelian group has a unique element of order $$2$$ then it equals the product of all the elements; otherwise the product is $$1$$, e.g. see here for hints (this is the group-theoretic Wilson 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 which shows 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.

• What on earth is an elt? Mar 12, 2022 at 22:09
• @Buraian If you Google "math abbrev elt" you'll see it means "element" Mar 12, 2022 at 23:21

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 Jul 21, 2010 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, 2010 at 18:44
• Beautiful proof! Well explained! Dec 24, 2018 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}]=[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]=[1]$,
or$[p-1]^2=[1]$.
Assume that there exists an element $[a],2\leq a \leq p-2$, such that $[a]^2=[1]$,
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 [1] and [p-1] are self-paired.
Therefore, consider the product: $x=[1]...[p-1]$,
Apart from $[1]$ and $[p-1]$, all other elements are paired together with their inverses,
so $x=[(p-1)!]=[p-1]\neq [1]$,
or $[(p-1)!]\neq [1]$.
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.

I will demonstrate from left to right. Suppose that n is a composite, then there exists a k, such that n=kq with 1<k<n, but clearly k also divides (n-2)!, so that (n-2)!=kd. Now given the congruence we have, it leaves us that kd ≡ 1 (mod kq) by definition we have that kd-1=kqt (definition of congruence) -1=kqt-kd 1=k(d-qt) Therefore k|1 and this only occurs if k=-1 or k=1. But we had assumed that 1<k<n (contradiction), therefore n is prime.

Here is a pretty 'intuitive' proof that I thought of. Consider the set $$S= \{1,2...,p-1\}$$ , we can this set equipped with modulo $$p$$ multiplication forms a group. Suppose we multiplied all the elements in the group together by the binary operation, we have:

$$1 \cdot 2 \cdot 3... \cdot (p-1) \equiv p-1 \mod p$$

This is due to the fact that the group is abelian, and, the only elements which are self inverses are $$\{1, p-1 \}$$. All the other elements get multiplied by their inverse and sent to identity.

## Proof that $${1,p-1}$$ are only self inverses:

Let $$k^2 \mod p =1$$ for $$k \in S$$, then

$$\implies (k+1)(k-1) \mod p = 0$$

$$\implies k+1 \mod p =0$$ ,or, $$k-1 \mod p =0$$

meaning $$k \mod p \in \{p-1,1 \}$$ where the $$k \mod p= -1$$ corresponds to $$k = p-1$$

QED

• Hmm what was the downvote for..? Mar 12, 2022 at 18:31
• Not mine, but likely because it duplicates prior answers (here and elsewhere). Mar 12, 2022 at 23:22