# Is this a good proof of Wilson's theorem? — ($(n-1)!+1 \equiv_n 0$ iff n is prime)

Theorem: $(n - 1)! + 1 \equiv_n 0$ if and only if $n$ is prime.

To prove that if $n$ is not prime this is not true is trivial, so I'm just interested in proving that this is true for all p:

EQ 1: $(n - 1)! \equiv_n - 1 \rightarrow (n-1)! \equiv_n (n-1)$

Now we need Euler's theorem of the Euler totient function:

Lemma 1: if $GCD(a, b) = 1$, then $a^{\varphi(b)} \equiv_b 1$.

By raising each side of EQ 1 to $\varphi(n)$, we see that the equivalence can hold if and only if $n$ is prime:

$(n-1)!^{\varphi(n)} \equiv_n (n-1)^{\varphi(n)}$

Because $(n-1)!$ would certainly have a common divisor with $n$ if n were composite.

-
There is no progress in showing that the result is true if $p$ is prime. Certainly it is enough to show that for any prime $p$, $(p-1)! \equiv p-1 \pmod{p}$. But writing this congruence down and then manipulating will not produce a proof. Your argument does show that if $n$ is composite then the desired congruence does not hold, but that is something you already had a simpler proof of. –  André Nicolas Oct 6 '11 at 1:05
Why does it not show that, if $n$ is prime, $(n-1)!^{\varphi(n)} \equiv_n (n-1)^{\varphi(n)}$ holds (and therefore the original equation)? — $(n-1)^{\varphi(n)} \equiv_n 1$ for any number, right? But $(n-1)!^{\varphi(n)} \equiv_n 1$ only if $GCD(n, (n-1)!) = 1$, which is always true if $n$ is prime. So it shows that if $n$ is prime the equality is true, and that if the equality is true $n$ is prime (because it's not true for a composite). So what am I missing? :( –  iDontKnowBetter Oct 6 '11 at 1:16
If $n$ is prime, it is indeed true that your congruence (the one with the $\varphi(n)$ as an exponent) holds. But from this we cannot conclude that $(n-1)! \equiv n-1 \pmod{n}$. In general, from $a^{p-1} \equiv b^{p-1}\pmod{p}$, we cannot conclude that $a \equiv b \pmod{p}$. Indeed almost the opposite is true: $a^{p-1}\equiv b^{p-1}\pmod{p}$ for almost all pairs $(a,b)$. –  André Nicolas Oct 6 '11 at 1:43
Oh, ok. Thanks. –  iDontKnowBetter Oct 6 '11 at 2:32

It seems to me from your last sentence ("if $n$ were composite") you're still showing that if $n$ is composite then the congruence doesn't hold, and that, as you know, is the easy direction. You want to start from the assumption that $n$ is prime, and deduce the congruence.
No, see Andre's comment on the original question. You have to prove that if $n$ is prime then the original congruence holds, not the one you have derived from it, which may not be equivalent to it. It's like saying $-3$ is a solution of $2x=6$ because it's a solution of the equation $4x^2=36$ that you get by squaring both sides. You may have introduced extraneous solutions. –  Gerry Myerson Oct 6 '11 at 1:14
But isn't it true that if $a \equiv_n b$, then $a^k \equiv_n b^k$? That's all I'm doing, then making the argument that, since $a^k \equiv_n b^k$ holds if n is prime, then it must follow that $a \equiv_n b$ must also hold if $n$ is prime. — Sorry if I'm being dense, but I just fail to see exactly where I make a false assumption. –  iDontKnowBetter Oct 6 '11 at 1:39
Yes, if $a\equiv b\pmod n$, then $a^k\equiv b^k\pmod n$. But for your argument to work, what you need is that if $a^k\equiv b^k\pmod n$, then $a\equiv b\pmod n$. Look at my example: if $2x=6$, then $4x^2=36$; but $4x^2=36$ doesn't imply $2x=6$. –  Gerry Myerson Oct 6 '11 at 2:17