Der Satz von Wilson

Eine natürliche Zahl $p>1$ ist genau dann eine Primzahl, wenn

durch $p$ teilbar ist.

Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren:

Ist $n$ eine zusammengesetzte Zahl mit $n=p\cdot q$, mit $p,q>1$, so gilt $p|(n-1)!$, und $p\nteiler (n-1)!+1$ und somit $n\nteiler (n-1)!+1$.

Bleibt zu zeigen, dass die Behauptung für Primzahlen gilt.

Der folgende Beweis beruht darauf, dass für ungerade Primzahlen $p$ die Menge $(\mathbb{Z} {/}p \mathbb{Z})^{\times} = \{ 1, 2, 3, \dots, p-1 \}$ unter der Multiplikation modulo $p$ eine Gruppe bildet. Also existiert zu jedem $a \in (\mathbb{Z} {/}p \mathbb{Z})^{\times}$ ein eindeutiges $\bar a \in (\mathbb{Z} {/}p \mathbb{Z})^{\times}$ mit $a \cdot \bar a \equiv 1 \, (\mathrm{mod}\, p)$.

Denn tritt der Fall $a \equiv \bar a \, (\mathrm{mod}\, p)$ auf, kann man beide Seiten der Kongruenz mit a multiplizieren und erhält $a^2 \equiv 1 \, (\mathrm{mod}\, p)$, also $a^2 - 1 = (a-1)(a+1) \equiv 0 \, (\mathrm{mod}\, p)$.

Weil p eine Primzahl ist, folgt aber aus $p|(a-1)(a+1)$ unmittelbar $p|(a-1)$ oder $p|(a+1)$, also $a = 1$ oder $a = p-1$.

Nun zum eigentlichen Beweis:

Für $p = 2$ ($2|1+1$) oder $p = 3$ ($3|2+1$) ergibt sich der Satz durch nachrechnen. Also kann man im folgenden $p\ge 5$ annehmen.

Nun ist $1 \equiv 1 \, (\mathrm{mod}\, p)$ und $p-1 \equiv -1 \, (\mathrm{mod}\, p)$.

Für alle $a \in \mathbb{N}$ mit $1 < a < p-1$ gilt aber $\mathrm{ggT}(a,p) = 1$, weil $p$ eine Primzahl ist.

Also existiert ein eindeutiges $\bar a \in \mathbb{N}$ mit $1 < \bar a < p-1$ und $a \cdot \bar a \equiv 1 \, (\mathrm{mod}\, p)$.

Durch Paarung dieser Reste modulo p erhält man:

$\prod\limits_{a=2}^{p-2} a \equiv 1 \, (\mathrm{mod}\, p)$, also $(p-1)! = 1 \cdot \prod\limits_{a=2}^{p-2} a \cdot (p-1) \equiv -1 \, (\mathrm{mod}\, p)$. $\qed$

Primzahlen $p$, bei denen $(p-1)!+1$ sogar durch $p^2$ teilbar ist, heißen Wilson-Primzahlen.

Ist allgemein $n$ eine beliebige natürliche Zahl, so gilt mit dem obigen Satz $(n-1)!\equiv -1 \mod n$ falls $n$ prim ist.

Für $n=4$ gilt $(n-1)!\equiv 2 \mod n$ und für alle zusammengesetzten Zahlen $n>5$ gilt $(n-1)!\equiv 0 \mod n$. Sie sind also stets Teiler von $(n-1)!$.

Ist also $n>4$ und $(n-1)!$ nicht durch $n$ teilbar, so ist $n$ eine Primzahl. Ist $(n-1)!$ aber durch $n$ teilbar, so erhält man aus dem Satz von Wilson die Information, dass $n$ zusammengesetzt ist, ohne eine konkrete Faktorisierung $n=ab$ mit $a,b\ne1$ zu kennen. Allerdings ist der Rechenaufwand für die Fakultät nicht geringer als Probedivisionen.