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