Der Satz von Wilson

Satz 1658 (Satz von Wilson)

Eine natürliche Zahl \(\displaystyle p>1\) ist genau dann eine Primzahl, wenn
\(\displaystyle (p-1)! + 1 \, \\)
durch \(\displaystyle p\) teilbar ist.
Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren:
(1)
\(\displaystyle (p-1)!\equiv-1\pmod p\, \)

Beweis

Ist \(\displaystyle n\) eine zusammengesetzte Zahl mit \(\displaystyle n=p\cdot q\), mit \(\displaystyle p,q>1\), so gilt \(\displaystyle p|(n-1)!\), und \(\displaystyle p\nteiler (n-1)!+1\) und somit \(\displaystyle 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 \(\displaystyle p\) die Menge \(\displaystyle (\mathbb{Z} {/}p \mathbb{Z})^{\times} = \{ 1, 2, 3, \dots, p-1 \} \) unter der Multiplikation modulo \(\displaystyle p\) eine Gruppe bildet. Also existiert zu jedem \(\displaystyle a \in (\mathbb{Z} {/}p \mathbb{Z})^{\times} \) ein eindeutiges \(\displaystyle \bar a \in (\mathbb{Z} {/}p \mathbb{Z})^{\times} \) mit \(\displaystyle a \cdot \bar a \equiv 1 \, (\mathrm{mod}\, p) \).
Denn tritt der Fall \(\displaystyle a \equiv \bar a \, (\mathrm{mod}\, p) \) auf, kann man beide Seiten der Kongruenz mit a multiplizieren und erhält \(\displaystyle a^2 \equiv 1 \, (\mathrm{mod}\, p) \), also \(\displaystyle a^2 - 1 = (a-1)(a+1) \equiv 0 \, (\mathrm{mod}\, p) \).
Weil p eine Primzahl ist, folgt aber aus \(\displaystyle p|(a-1)(a+1) \) unmittelbar \(\displaystyle p|(a-1) \) oder \(\displaystyle p|(a+1) \), also \(\displaystyle a = 1 \) oder \(\displaystyle a = p-1 \).
Nun zum eigentlichen Beweis:
Für \(\displaystyle p = 2\) (\(\displaystyle 2|1+1\)) oder \(\displaystyle p = 3\) (\(\displaystyle 3|2+1\)) ergibt sich der Satz durch nachrechnen. Also kann man im folgenden \(\displaystyle p\ge 5\) annehmen.
Nun ist \(\displaystyle 1 \equiv 1 \, (\mathrm{mod}\, p) \) und \(\displaystyle p-1 \equiv -1 \, (\mathrm{mod}\, p) \).
Für alle \(\displaystyle a \in \mathbb{N} \) mit \(\displaystyle 1 < a < p-1 \) gilt aber \(\displaystyle \mathrm{ggT}(a,p) = 1 \), weil \(\displaystyle p\) eine Primzahl ist.
Also existiert ein eindeutiges \(\displaystyle \bar a \in \mathbb{N} \) mit \(\displaystyle 1 < \bar a < p-1 \) und \(\displaystyle a \cdot \bar a \equiv 1 \, (\mathrm{mod}\, p) \).
Durch Paarung dieser Reste modulo p erhält man:
\(\displaystyle \prod\limits_{a=2}^{p-2} a \equiv 1 \, (\mathrm{mod}\, p) \), also \(\displaystyle (p-1)! = 1 \cdot \prod\limits_{a=2}^{p-2} a \cdot (p-1) \equiv -1 \, (\mathrm{mod}\, p) \). \(\displaystyle \qed\)
 
 

Bemerkungen

Primzahlen \(\displaystyle p\), bei denen \(\displaystyle (p-1)!+1\) sogar durch \(\displaystyle p^2\) teilbar ist, heißen Wilson-Primzahlen.
Ist allgemein \(\displaystyle n\) eine beliebige natürliche Zahl, so gilt mit dem obigen Satz \(\displaystyle (n-1)!\equiv -1 \mod n\) falls \(\displaystyle n\) prim ist.
Für \(\displaystyle n=4\) gilt \(\displaystyle (n-1)!\equiv 2 \mod n\) und für alle zusammengesetzten Zahlen \(\displaystyle n>5\) gilt \(\displaystyle (n-1)!\equiv 0 \mod n\). Sie sind also stets Teiler von \(\displaystyle (n-1)!\).
Ist also \(\displaystyle n>4\) und \(\displaystyle (n-1)!\) nicht durch \(\displaystyle n\) teilbar, so ist \(\displaystyle n\) eine Primzahl. Ist \(\displaystyle (n-1)!\) aber durch \(\displaystyle n\) teilbar, so erhält man aus dem Satz von Wilson die Information, dass \(\displaystyle n\) zusammengesetzt ist, ohne eine konkrete Faktorisierung \(\displaystyle n=ab\) mit \(\displaystyle a,b\ne1\) zu kennen. Allerdings ist der Rechenaufwand für die Fakultät nicht geringer als Probedivisionen.

Die Furcht vor der Mathematik steht der Angst erheblich näher als der Ehrfurcht.

Felix Auerbach

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе