I need to show that if $(n-2)! \equiv 1 \pmod n$ then $n$ is prime.
I think that if $n$ is composite, then we'll have every factor of $n$ in $(n-2)!$, and it would yield that $(n-2)! \equiv 0 \pmod n$.
However, I didn't use the fact that it specifically congruent to $1 \bmod n$, so I think I'm getting something fundamental wrong. Is my solution correct? Why do we demand congruence to $1 \bmod n$?
[Math] Showing a number $n$ is prime if $(n-2)! \equiv 1 \pmod n$
congruenceselementary-number-theory
Best Answer
Your solution is correct aside from the small detail of 4!, which has already been pointed out in the comments. 4 is somewhat special, being the first composite number, and the square of the "oddest" prime. So I don't think this little mistake is at all "fundamental."
Still, I think it's better to use the fact of $1 \bmod n$, since it guarantees that $\gcd((n! - 2), n) = 1$. The least prime factor of $n$, if $n$ is not itself prime, is less than or equal to $\sqrt n$, and $\sqrt n < (n - 2)$ for all $n > 4$. Therefore, if $n$ is composite, then $(n - 2)!$ is divisible by the least prime factor of $n$, making $(n - 2)! \equiv 1 \bmod n$ impossible.
Yet another way you can go about it is this: If $n$ is even and composite, then $n - 2$ is also even and therefore $(n - 2)! \equiv 2k \bmod n$, where $k$ is some nonnegative integer we don't care too much about. But 1 is not even, proving $n$ is not an even composite number. If $n$ is odd and composite, it is divisible by some odd prime $p \leq \sqrt n$. And since $p \leq \sqrt n < (n - 2)$, it follows that $p \mid (n - 2)!$ and $(n - 2)! \equiv pk \bmod n$. And $pk \neq 1$, proving $n$ is not an odd composite number.
And yet another way is to use Wilson's theorem, but then I would be merely restating one or two of the other answers.