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

Question

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

Thanks.

Answer 1

$$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).

Answer 2

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.

Answer 3

[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.

Answer 4

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.