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.

Theorem: $(n - 1)! + 1 \equiv_n 0$ if and only if $n$ is prime.

To prove that if $n$ is not prime this is not true is trivial, so I'm just interested in proving that this is true for all p:

EQ 1: $(n - 1)! \equiv_n - 1 \rightarrow (n-1)! \equiv_n (n-1) $

Now we need Euler's theorem of the Euler totient function:

Lemma 1: if $GCD(a, b) = 1$, then $a^{\varphi(b)} \equiv_b 1$.

By raising each side of EQ 1 to $\varphi(n)$, we see that the equivalence can hold if and only if $n$ is prime:

$(n-1)!^{\varphi(n)} \equiv_n (n-1)^{\varphi(n)}$

Because $(n-1)!$ would certainly have a common divisor with $n$ if n were composite.

share|improve this question
2  
There is no progress in showing that the result is true if $p$ is prime. Certainly it is enough to show that for any prime $p$, $(p-1)! \equiv p-1 \pmod{p}$. But writing this congruence down and then manipulating will not produce a proof. Your argument does show that if $n$ is composite then the desired congruence does not hold, but that is something you already had a simpler proof of. –  André Nicolas Oct 6 '11 at 1:05
    
Why does it not show that, if $n$ is prime, $(n-1)!^{\varphi(n)} \equiv_n (n-1)^{\varphi(n)}$ holds (and therefore the original equation)? — $(n-1)^{\varphi(n)} \equiv_n 1$ for any number, right? But $(n-1)!^{\varphi(n)} \equiv_n 1$ only if $GCD(n, (n-1)!) = 1$, which is always true if $n$ is prime. So it shows that if $n$ is prime the equality is true, and that if the equality is true $n$ is prime (because it's not true for a composite). So what am I missing? :( –  iDontKnowBetter Oct 6 '11 at 1:16
    
If $n$ is prime, it is indeed true that your congruence (the one with the $\varphi(n)$ as an exponent) holds. But from this we cannot conclude that $(n-1)! \equiv n-1 \pmod{n}$. In general, from $a^{p-1} \equiv b^{p-1}\pmod{p}$, we cannot conclude that $a \equiv b \pmod{p}$. Indeed almost the opposite is true: $a^{p-1}\equiv b^{p-1}\pmod{p}$ for almost all pairs $(a,b)$. –  André Nicolas Oct 6 '11 at 1:43
    
Oh, ok. Thanks. –  iDontKnowBetter Oct 6 '11 at 2:32

1 Answer 1

It seems to me from your last sentence ("if $n$ were composite") you're still showing that if $n$ is composite then the congruence doesn't hold, and that, as you know, is the easy direction. You want to start from the assumption that $n$ is prime, and deduce the congruence.

share|improve this answer
    
Would it be correct then if I added "and if n is prime, the equation always holds"? — Does the last equation prove this? It seems to me it does. –  iDontKnowBetter Oct 6 '11 at 0:53
    
No, see Andre's comment on the original question. You have to prove that if $n$ is prime then the original congruence holds, not the one you have derived from it, which may not be equivalent to it. It's like saying $-3$ is a solution of $2x=6$ because it's a solution of the equation $4x^2=36$ that you get by squaring both sides. You may have introduced extraneous solutions. –  Gerry Myerson Oct 6 '11 at 1:14
    
But isn't it true that if $a \equiv_n b$, then $a^k \equiv_n b^k$? That's all I'm doing, then making the argument that, since $a^k \equiv_n b^k$ holds if n is prime, then it must follow that $a \equiv_n b$ must also hold if $n$ is prime. — Sorry if I'm being dense, but I just fail to see exactly where I make a false assumption. –  iDontKnowBetter Oct 6 '11 at 1:39
    
Yes, if $a\equiv b\pmod n$, then $a^k\equiv b^k\pmod n$. But for your argument to work, what you need is that if $a^k\equiv b^k\pmod n$, then $a\equiv b\pmod n$. Look at my example: if $2x=6$, then $4x^2=36$; but $4x^2=36$ doesn't imply $2x=6$. –  Gerry Myerson Oct 6 '11 at 2:17
    
I see now. Thanks. –  iDontKnowBetter Oct 6 '11 at 2:32

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.