# How to show that $n$ is a prime?

Suppose that $n>1$ satisfies $(n-1)! \equiv -1 \pmod n$. Show that $n$ is a prime. (Hint: Antithesis)

My own trying: $n=3$: $(3-1)!+1= 3 \cdot 1$ => $3|2!+1$. $n=5$: $(5-1)!+1=25 = 5 \cdot 5$ => $5|4!+1$. $n=7$: $(7-1)!+1=3 = 720+1 = 7 \cdot 103$ => $7|6!+1$. So at least it holds for $n=3, 5$ and $7$. But how to prove it?

-
Hint: Suppose to the contrary that $n=ab$ where $a>1$, $b>1$. Then $a \le n-1$, so $a$ divides $(n-1)!$. – André Nicolas Sep 19 '11 at 16:04
@alv By the way, I think you should consider accepting some answers to your previous questions. – Srivatsan Sep 19 '11 at 16:09
@André: How do you get from $a>1, b>1$ that $a \leq n-1$ and that a divides $(n-1)!$? – alvoutila Sep 19 '11 at 16:25
But once check my proof – Iyengar Sep 19 '11 at 16:31
Your calculations show that $(p-1)! \equiv -1 \pmod{p}$ for the first few primes $p$. Even if you went on to prove that $(p-1)!\equiv -1 \pmod{p}$ for all primes $p$, this would still not prove that if $n>1$ and $(n-1)! \equiv -1\pmod{n}$, then $n$ is prime. The question you were asked is whether the congruence can hold at a composite $n$, not whether it holds at primes. (Actually, the congruence holds at all primes, and fails at all non-primes $>1$. The proof that the congruence holds at all primes is quite a bit harder than the proof it fails at all composite numbers.) – André Nicolas Sep 19 '11 at 17:05

We will show that if $(n-1)! \equiv -1 \pmod{n}$, and $n>1$, then $n$ is prime.

Let $a$ be any (positive) divisor of $n$ which is not equal to $n$. Then $a \le n-1$. So $a$ is one of the numbers which get multiplied together to form $(n-1)!$. It follows that $a$ divides $(n-1)!$.

Suppose now $(n-1)! \equiv -1\pmod{n}$. Then, by the definition of congruence modulo $n$, $n$ divides $(n-1)!+1$. But since $a$ divides $n$, the fact that $n$ divides $(n-1)!+1$ implies that $a$ divides $(n-1)!+1$.

But $a$ divides $(n-1)!$. Since $a$ divides both $(n-1)!+1$ and $(n-1)!$, it follows that $a$ divides the difference between these two numbers. But this difference is $1$. So $a$ divides $1$, and therefore $a=1$.

We have shown that if $a$ is any (positive) divisor of $n$ such that $a \ne n$, then $a$ must be equal to $1$. Since $n>1$, this forces $n$ to be prime, by the definition of prime. (The primes are precisely the numbers $n>1$ whose only positive divisors are $n$ and $1$. We have shown that if our congruence holds, and $a$ is a positive divisor of $n$ such that $a \ne n$, then $a=1$.)

-
But did you used antithesis in your proof to show that then $(n-1)! \notequiv -1( \pmod n)$ – alvoutila Sep 19 '11 at 17:01
@alvoutila: If you want to use that wording, change the answer slightly. Write "Suppose to the contrary that $(n-1)!\equiv -1 \pmod{n}$." Then proceed exactly like in the answer above to show that $n$ is prime. That gets you your desired contradiction. I avoided a proof by contradiction in the hope that that would make the logic clearer. – André Nicolas Sep 19 '11 at 17:31
But did you used antithesis in your proof to show that then $(n−1)! \not \equiv −1(\pmod n)$? Would you please show some hint on how to prove this that way by antithesis? – alvoutila Sep 19 '11 at 17:56
I described, in comment above, exactly how to turn the answer into an explicit proof by contradiction (antithesis). It involves adding the sentence in quotes at the beginning, (together with $n>1$ not prime), then appending the proof I wrote, and then saying we have reached a contradiction. – André Nicolas Sep 19 '11 at 18:55
But in my opinion proof by antithesis would as following: AT. suppose that n be not prime( not: suppose that $(n-1)! \equiv -1\pmod n$ )... => $(n-1)! \not \equiv -1\pmod n$. Isn't it? – alvoutila Sep 19 '11 at 19:13

If $n=ab$ is composite, what can you say about $a$ and $b$? Relate that to $(n-1)!$.

Here is the full answer: If $n=ab$ is a non-trivial factorization, then $a<n$ and $b<n$, and so $a\le n-1$ and $b\le n-1$. But then both $a$ and $b$ appear in $(n-1)!$ and so $(n-1)!\equiv 0 \pmod{n}$.

-
The argument does not work for $n=4$ but then it's obvious that $(4-1)! \equiv 2 \pmod 4$. See en.wikipedia.org/wiki/… – lhf Sep 27 '11 at 16:44