Satz von Wilson

Der Satz von Wilson (benannt nach John Wilson) ist ein mathematischer Satz aus der Zahlentheorie. Er macht Teilbarkeitsaussagen zu den natürlichen bzw. ganzen Zahlen und wird deswegen auch der elementaren Zahlentheorie zugeordnet, mit deren Methoden er auch bewiesen werden kann.

Aussage

Der Satz von Wilson besagt: Eine natürliche Zahl ${\displaystyle p\geq 2}$ ist genau dann eine Primzahl, wenn ${\displaystyle (p-1)!+1}$ durch ${\displaystyle p}$ teilbar ist. Dabei bezeichnet ${\displaystyle (p-1)!}$ das Produkt ${\displaystyle 1\cdot 2\cdot 3\cdots (p-1)}$.

Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren: Ist ${\displaystyle p\geq 2}$ eine natürliche Zahl, so gilt

${\displaystyle (p-1)!\equiv -1{\pmod {p}}\Longleftrightarrow p\ \mathrm {ist} \ \mathrm {prim.} }$

Umgekehrt kann man mit dem Satz auch schließen: Sei ${\displaystyle n\geq 2}$ eine natürliche Zahl, so gilt

${\displaystyle (n-1)!\equiv {\begin{cases}n-1{\pmod {n}},&\mathrm {falls} \ n\ \mathrm {Primzahl} ,\\2{\pmod {n}},&\mathrm {falls} \ n=4,\\0{\pmod {n}},&\mathrm {sonst} .\end{cases}}}$

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\neq 1}$ zu kennen. Allerdings ist der Rechenaufwand für die Fakultät nicht geringer als Probedivisionen.

Direkter Beweis

Ist ${\displaystyle p}$ eine Primzahl, so ist der Restklassenring ${\displaystyle \mathbb {Z} /(p)=\{{\overline {0}},\ldots ,{\overline {p-1}}\}}$ ein Körper, in dem ${\displaystyle {\overline {1}}}$ und ${\displaystyle {\overline {p-1}}}$ die einzigen zu sich selbst inversen Elemente sind. Daher kommt im Produkt ${\displaystyle {\overline {2}}\cdot {\overline {3}}\cdot \ldots \cdot {\overline {p-2}}}$ jeder Faktor zusammen mit seinem inversen Element vor, weshalb das Produkt gleich ${\displaystyle {\overline {1}}}$ ist. Das bedeutet aber gerade ${\displaystyle (p-2)!\equiv 1{\pmod {p}}}$, woraus ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$ folgt. Ist umgekehrt ${\displaystyle n>4}$ keine Primzahl, so gibt es Faktoren ${\displaystyle 1<a,b\leq n-2}$ mit ${\displaystyle n=a\cdot b}$. Daher ist ${\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {0}}}$ und ${\displaystyle {\overline {a}}\cdot {\overline {2b}}={\overline {0}}}$, jedenfalls gibt es im Produkt ${\displaystyle {\overline {2}}\cdot {\overline {3}}\cdot \ldots \cdot {\overline {n-2}}}$ zwei Faktoren, deren Produkt ${\displaystyle {\overline {0}}}$ ist, weshalb das gesamte Produkt in ${\displaystyle \mathbb {Z} /(n)}$ verschwinden muss. Das bedeutet aber ${\displaystyle (n-2)!\equiv 0{\pmod {n}}}$ und erst recht ${\displaystyle (n-1)!\equiv 0{\pmod {n}}}$.

Anmerkungen

• Für jede natürliche Zahl ${\displaystyle n\geq 2}$ ist jede der beiden Kongruenzen ${\displaystyle (n-2)!\equiv 1{\pmod {n}}}$ und ${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$ genau dann erfüllt, wenn die jeweils andere erfüllt ist. Man gewinnt dabei die eine aus der anderen (und vice versa) durch Rechtsmultiplikation mit ${\displaystyle -1}$, indem man berücksichtigt, dass für ${\displaystyle n\in N}$ und ${\displaystyle n\geq 2}$ stets die Kongruenzen ${\displaystyle n-1\equiv -1{\pmod {n}}}$ und ${\displaystyle (n-1)\cdot (-1)\equiv (-1)^{2}\equiv 1{\pmod {n}}}$ gelten. Der Satz von Wilson ist also gleichwertig zu der bei Sierpiński^[1] als „Leibniz’ Theorem“ bezeichneten Formulierung

Eine natürliche Zahl ${\displaystyle n\geq 2}$ ist eine Primzahl dann und nur dann, wenn sie die Kongruenz

${\displaystyle (n-2)!\equiv 1{\pmod {n}}}$

erfüllt.

• Von Fischer/Sacher – wie auch von anderen Autoren – wird als Satz von Wilson lediglich die Kongruenzaussage für Primzahlen ${\displaystyle p\in \mathbb {N} }$ zitiert.

Beispiele

Die folgende Tabelle zeigt die Werte von n von 2 bis 30, (n-1)! und den Rest von (n-1)! modulo n. Wenn n eine Primzahl ist, dann ist die Hintergrundfarbe pink. Und wenn n eine zusammengesetzte Zahl ist, dann ist die Hintergrundfarbe hellgrün.

Geschichte

Das heute als Satz von Wilson bekannte Resultat wurde erstmals von Ibn al-Haytham entdeckt, aber schließlich nach John Wilson (einem Studenten des englischen Mathematikers Edward Waring) benannt, der es mehr als 700 Jahre später wiederentdeckte. Waring veröffentlichte diesen Satz im Jahr 1770, obwohl weder er noch Wilson einen Beweis erbringen konnten. Joseph Louis Lagrange gab den ersten Beweis 1773.

Nach Dietrich Mahnke besteht Grund zur Annahme, dass Gottfried Wilhelm Leibniz ein Jahrhundert zuvor von diesem Resultat wusste, es aber niemals publizierte. In einem aus dem Jahr 1683 stammenden Manuskript bewies Leibniz den Kleinen Satz von Fermat und erwähnte auch die für Primzahlen ${\displaystyle p}$ zum Satz von Wilson äquivalente (und von Sierpiński als „Leibniz’ Theorem“ bezeichnete) Tatsache, dass ${\displaystyle (p-2)!\equiv 1{\pmod {p}}}$ ist, wobei er fälschlich behauptete, dass der Rest 1 oder −1 sein könnte. Mahnke führt in „Leibniz auf der Suche nach einer allgemeinen Primzahlgleichung“^[2] auf Seite 42 aus:

„Leibniz hat in der Tat, wie Vacca im Boll. di bibl. e storia mat. 1899 festgestellt hat, den Wilsonschen Satz schon etwa ein Jahrhundert eher erkannt als Waring ihn in seinen Meditationes algebraicae (Cantabrigiae 1770) veröffentlicht und Lagrange an der angegebenen Stelle ihn zuerst bewiesen hat. Leibniz hat nämlich in Handschrift 25 die Reste von 1!,2!,3!,...,16! mod 17, ferner die Reihe mod 3, mod 4,...,mod 17 zusammengestellt und daraus geschlossen [...] D.h. (p-2)!=1 mod p, wenn p eine Primzahl ist, dagegen (n-2)!=m mod n, wobei m einen gemeinsamen Faktor mit n besitzt. Würde man die erste Kongruenz mit p-1 multiplizieren, so [...] würde der bekannte Wilsonsche Satz folgen. Leibniz hat nun seinen induktiv gefundenen Satz noch bei der nächsten Primzahl, p=17, nachgeprüft, sich dabei aber verrechnet. Er gibt nämlich an 11!=16,...,15!=16,16!=1 mod 17, während in Wirklichkeit 11!=1,...15!=1,16!=16 mod 17 ist. Durch diesen Rechenfehler ist er veranlasst worden, seinen richtigen Satz abzuändern und noch den falschen Zusatz zu machen: „... relinquish [1 vel complementum ad 1]“, d. h. p-1. In der Tat ist ja bei seiner Rechnung 15!=17-1, während in Wirklichkeit 15!=1 mod 17 ist. So erklärt sich dieser falsche Zusatz, der Vacca unverständlich war.“

Korollare

• Ist ${\displaystyle n}$ das Produkt von 2 mit einer Primzahl, so gilt auch:

${\displaystyle \varphi (n)!\equiv \varphi (n)\mod {n}}$

Ansonsten ist das Ergebnis kongruent zu Null.

${\displaystyle \varphi }$ bezeichnet dabei die eulersche Phi-Funktion

• Ein weiteres Korollar bezieht sich auf eine Summe von Produkten, in denen jeweils eine Fakultät als Faktor enthalten ist:

${\displaystyle p}$ ist genau dann eine Primzahl, wenn die Summe ${\displaystyle s=\sum _{k=1}^{p-3}k\cdot k!}$ durch ${\displaystyle p}$ teilbar ist.

Beweis:

${\displaystyle s=1\cdot 1!+2\cdot 2!+...+(p-3)\cdot (p-3)!}$

Wegen ${\displaystyle k\cdot k!=(k+1-1)\cdot k!=(k+1)!-k!}$ folgt:

${\displaystyle s=(2!-1!)+(3!-2!)+(4!-3!)+...+((p-2)!-(p-3)!)=(p-2)!-1}$

Es gilt folgende Äquivalenzkette:

${\displaystyle s=(p-2)!-1|\cdot (p-1)}$

${\displaystyle \Leftrightarrow (p-1)\cdot s=(p-1)!-(p-1)|+p}$

${\displaystyle \Leftrightarrow (p-1)\cdot s+p=(p-1)!+1}$ (1)

Nach dem Satz von Wilson ist ${\displaystyle p}$ genau dann eine Primzahl, wenn ${\displaystyle (p-1)!+1}$ durch ${\displaystyle p}$ teilbar ist.

Nach (1) ist demnach ${\displaystyle p}$ genau dann eine Primzahl, wenn ${\displaystyle (p-1)\cdot s+p}$ durch ${\displaystyle p}$ teilbar ist, was wiederum gleichbedeutend damit ist, dass ${\displaystyle (p-1)\cdot s}$ durch ${\displaystyle p}$ teilbar ist.

Da ${\displaystyle p-1}$ und ${\displaystyle p}$ teilerfremd sind, ist die letzte Aussage äquivalent dazu, dass ${\displaystyle p}$ die Summe ${\displaystyle s}$ teilt, was zu beweisen war.^[3][4]

Verallgemeinerungen

Es gilt allgemein:

${\displaystyle \prod _{\begin{matrix}1\leq a<m\\(a,m)=1\end{matrix}}a\ \equiv \ \left\{{\begin{matrix}-1\ ({\mbox{mod }}m),&{\mbox{wenn }}m=4,\;p^{\alpha },\;2p^{\alpha },\,\alpha \in \mathbb {N} ,\\\ \ 1\ ({\mbox{mod }}m)&{\mbox{sonst}}\end{matrix}}\right.}$

Eine leichte Verallgemeinerung des Satzes von Wilson lautet:

Eine Zahl ${\displaystyle p\in \mathbb {N} }$ ist genau dann Primzahl, wenn für alle ${\displaystyle 1\leq n\leq p}$

${\displaystyle (n-1)!(p-n)!\equiv (-1)^{n}\ \mathrm {mod} \ p}$

gilt. Dieser Satz lässt sich leicht mit vollständiger Induktion nach ${\displaystyle n}$ und mit dem Satz von Wilson beweisen. Für ${\displaystyle n=1}$ oder ${\displaystyle n=p}$ ergibt sich der Satz von Wilson. Setzt man hier ${\displaystyle n={\frac {p+1}{2}}}$, so ergibt sich:

${\displaystyle p\in \mathbb {N} }$ mit ${\displaystyle p>2}$ und ungerade ist genau dann Primzahl, wenn ${\displaystyle \left(\left({\frac {p-1}{2}}\right)!\right)^{2}\equiv (-1)^{\frac {p+1}{2}}\ \mathrm {mod} \ p}$.

Körpertheoretische Formulierung

Allgemeiner Satz

Der Satz von Wilson ist ein Spezialfall eines allgemeinen Satzes aus der Theorie der endlichen Körper, der sich wie folgt angeben lässt:^[5]

Ist ${\displaystyle K}$ ein endlicher Körper und ${\displaystyle K^{*}}$ seine Einheitengruppe,

so ist stets die Gleichung

${\displaystyle \prod \limits _{a\in K^{*}}{a}=-1}$

erfüllt.

Beweis des allgemeinen Satzes

Der Darstellung von Fischer/Sacher folgend kann man wie folgt argumentieren:^[6]

Die in ${\displaystyle K^{*}}$ gelegene Teilmenge

${\displaystyle M:=\{a\in K^{*}\mid a=a^{-1}\}=\{a\in K^{*}\mid a^{2}=1\}=\{a\in K^{*}\mid a^{2}-1=0\}}$

ist die Nullstellenmenge des Polynoms ${\displaystyle X^{2}-1\in K[X]}$ und wegen ${\displaystyle (X-1)(X+1)=X^{2}-1}$ gilt

${\displaystyle M=\{1,-1\}}$.

Andererseits ist offenbar

${\displaystyle \prod \limits _{a\in K^{*}}{a}=\prod \limits _{a\in M}{a}}$,

denn jedes Körperelement ${\displaystyle a\in K^{*}\setminus M}$ liefert in dem Produkt zusammen mit seinem Inversen stets den Beitrag ${\displaystyle 1}$.

Also gilt die behauptete Gleichung.

Verwandte Begriffe

Das nur für Primzahlen ${\displaystyle p}$ ganzzahlige Ergebnis der Division

${\displaystyle {\frac {(p-1)!+1}{p}}}$

wird als Wilson-Quotient ${\displaystyle W(p)}$ bezeichnet^[7] (Folge A007619 in OEIS).

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

Beispiel: 13 ist Wilson-Primzahl; denn ${\displaystyle (13-1)!+1=13^{2}\cdot 2\,834\,329}$.

Weblinks

Wikibooks: Beweis zum Satz von Wilson – Lern- und Lehrmaterialien

• Eric W. Weisstein: Wilson’s Theorem. In: MathWorld (englisch).

Einzelnachweise

1. ↑ Wacław Sierpiński: Elementary Theory of Numbers (= North-Holland Mathematical Library. Band 31). 2. überarbeitete und erweiterte Auflage. North-Holland (u. a.), Amsterdam (u. a.) 1988, ISBN 0-444-86662-0 (MR0930670). 
2. ↑ Dietrich Mahnke: "Leibniz auf der Suche nach einer allgemeinen Primzahlgleichung." Bibl. Math. 13 (1912-13), 29–61.
3. ↑ Ross Honsberger: Gitter - Reste - Würfel Friedrich Vieweg & Sohn Verlagsgesellschaft mbH, Braunschweig 1984, ISBN 978-3-528-08476-9, Seiten 34 und 35
4. ↑ Douglas Lind, Kenneth Kramer, Steven Minsker: Problem E 1702, American Mathematical Monthly, Los Angeles, (Kalifornien) (1965)
5. ↑ Gerd Fischer, Reinhard Sacher: Einführung in die Algebra. 1978, S. 162
6. ↑ Gerd Fischer, Reinhard Sacher: Einführung in die Algebra (= Teubner Studienbücher: Mathematik). 2. überarbeitete Auflage. B. G. Teubner, Stuttgart 1978, ISBN 3-519-12053-4 (MR0492996). 
7. ↑ Eric W. Weisstein: Wilson Quotient. In: MathWorld (englisch).