3
$\begingroup$

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.

  • 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.2011-10-06
  • 0
    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? :(2011-10-06
  • 0
    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)$.2011-10-06

1 Answers 1

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.

  • 0
    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.2011-10-06
  • 0
    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.2011-10-06
  • 0
    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.2011-10-06
  • 1
    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$.2011-10-06