how to prove that a natural number n > 1 is prime if and only if n divides (n-2)! - 1? I know it is a 'iff' questions so that it need to be proved by both directions, and I tried to prove by contradiction or contrapositive but still did not figure it out.
Asked
Active
Viewed 1,832 times
2 Answers
1
Wilson's theorem states that a natural number $n $ is a prime number if and only if $$(n-1)! \equiv -1 \pmod n$$
$$(n-1)(n-2)! \equiv -1 \pmod n$$
$$(n-2)! \equiv 1 \pmod n$$
Guy Fsone
- 23,903
1
Wilson's Theorem:
$n$ is prime $\Leftrightarrow (n-1)!+1\equiv 0(\mod n)$
But as $(n-1)!+1\equiv(n-1)((n-2)!-1)(\mod n)$ and gcd$(n,n-1)=1$, then
$(n-2)!-1\equiv0(\mod n) \Leftrightarrow (n-1)!+1\equiv0(\mod n) \Leftrightarrow n$ is prime
asdf
- 4,587
$$(n-1)(n-2)! \equiv -1 \pmod n$$
– Guy Fsone Feb 07 '18 at 20:58