Prove the converse of Wilson's Theorem [duplicate]

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime.

This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it concretely..

Reason by contradiction, suppose that $n$ is not prime.

Then $n = ab$, where $1 < a, b < n$

In particular $(n-1)! = ai$ for some $i\in\Bbb{Z}$. $\\$ If $(n-1)! = nj - 1$ for some $j\in\Bbb{Z}$ then it follows that a probably doesn't divide $-1$?

Solution 1:

You have the basic idea, and got almost to the end.

Let $n$ be composite. Then there exist integers $a$, $b$, with $1\lt a \lt n$, such that $ab=n$. Since $a\ne n$, it follows that $a$ divides $(n-1)!$.

If the "Wilson" congruence holds for $n$, then $(n-1)!\equiv -1\pmod{n}$. Thus $(n-1)!=qn-1$ for some $q$.

But $a$ divides both $(n-1)!$ and $n$. It follows that $a$ divides $-1$. This is impossible, since $a\gt 1$. So we have shown that if $n$ is composite, we cannot have $(n-1)!\equiv -1\pmod{n}$.