Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
3  
@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)!$? –  laovultai Sep 19 '11 at 16:25
    
But once check my proof –  Iyengar Sep 19 '11 at 16:31
2  
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

2 Answers 2

up vote 3 down vote accepted

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$.)

share|improve this answer
    
But did you used antithesis in your proof to show that then $(n-1)! \notequiv -1( \pmod n)$ –  laovultai 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? –  laovultai 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? –  laovultai 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}$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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