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.

  • 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.

  • 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