# Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime

How can I show that $(n-1)!$ is congruent to $-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 congruent 1 (mod n). We show this as follows. Suppose n not | 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 in 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 congruent 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

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.

-

[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

HINT $\rm\ (p-1)!\ mod\ 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. The 2-cycles $\rm (n, n^{-1})$ have product 1 so they can be deleted from the product, leaving only the product of 1-cycles $\rm (n)$. They satisfy $\rm\: n^{-1} = n \Rightarrow n^2 = 1 \Rightarrow n = \pm 1\:$ via $\rm{\mathbb F}_p$ a field. So the product reduces to $\:-1*1 = -1$.

This generalizes: if a finite abelian group has a unique elt of order 2 then it is equal to the product of all the elts; otherwise the product is 1, e.g. see this thread for hints.

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.

-