1
$\begingroup$

I'm working through an exercise which involves Wilson's Theorem:

Let $n \in \mathbb{Z}$ with $n>1$. Prove that n is a prime number if and only if $(n-2)!\equiv 1 \pmod n$

So far I have :

($\rightarrow$) Suppose n is a prime number, by Wilson's theorem we know that $(n-1)!\equiv -1 \pmod n$. If we divide $(n-1)$ from both sides we get $(n-2)! \equiv 1 \pmod n$.

I'm not really sure how to get started on the opposite direction. Any hints?

$\endgroup$
1
$\begingroup$

Hint: if $n$ is not prime then it has a prime divisor $k \leq n/2$. If $n \geq 4$ then $n/2 \leq n-2$ and so $k \mid (n-2)!$, which contradicts $(n-2)! \equiv 1 \pmod{n}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$n$ is a prime iff $(n-1)!\equiv -1 \bmod n$. That's Wilson's theorem.

The result follows because $n-1\equiv -1 \pmod n$ :

In one direction, just cancel $n-1$ on the left with $-1$ on the right of $(n-1)!\equiv -1$.

In the other direction, just multiply both sides of $(n-2)!\equiv 1$ by $-1$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.