Sunday, 16 April 2017

$(p-1)! \equiv -1 \bmod p$

A group theoretic proof:

Obviously, for $p = 2$, the statement is true.
For the rest of the proof, let's assume $p \neq 2$

Now, if we have a finite abelian group $G = \{x_1, \dots , x_n\}$, we know that $x_1*x_2* \dots x_n = \prod\limits_{ord(x_i)=2}x_i$, because every element that does not have order 2 cancels with its inverse (if $ord(x) = 2$, then $x^2 = e$, then $x = x^{-1}$)

Now, let's apply this to the group $(\mathbb{Z}/p\mathbb{Z}-\{0\},.)$:

(Denote the elements of $\mathbb{Z}/p\mathbb{Z}-\{0\}$  as $\{ [1], \dots [p-1]\}$)

We find $$[1][2][3]\dots[p-1] = [(p-1)!] =\prod\limits_{ord(x_i)=2}x_i$$

So, we only have to find the elements of order 2 in the group:

Hence, let's solve the equation $[a]^2 = [1]$:

$[a]^2 = [1] \iff [a^2] = [1] \iff a^2 \equiv 1 \bmod p \iff p|(a-1)(a+1)$

and because $p$ is prime (that's important here), it follows that either $p|(a-1)$ or $p|(a+1)$. Hence, $a \equiv 1 \bmod p$ or $a \equiv -1 \bmod p$

and thus:

$[a] = [1]$ or $[a] = [-1]$

Because $ord([1]) = 1$, it follows that $[-1]$ is the only element of order $2$ in the group. Hence:

$[(p-1)!] = [-1]$

and thus:

$(p - 1)! \equiv -1 \bmod p \quad \triangle$