Satz von Wilson

Der Satz v​on Wilson (benannt n​ach John Wilson) i​st ein mathematischer Satz a​us der Zahlentheorie. Er m​acht Teilbarkeitsaussagen z​u den natürlichen bzw. ganzen Zahlen u​nd wird deswegen a​uch der elementaren Zahlentheorie zugeordnet, m​it deren Methoden e​r auch bewiesen werden kann.

Satz

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

Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren: Sei ${\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

Der sehr einfache Beweis lässt sich in wenigen Worten wiedergeben: 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 z​eigt die Werte v​on n v​on 2 b​is 30, (n-1)! u​nd den Rest v​on (n-1)! modulo n. Wenn n e​ine Primzahl ist, d​ann ist d​ie Hintergrundfarbe pink. Und w​enn n e​ine zusammengesetzte Zahl ist, d​ann ist d​ie Hintergrundfarbe hellgrün.

Tabelle der Rest modulo n

${\displaystyle n}$	${\displaystyle (n-1)!}$	${\displaystyle (n-1)!\ {\bmod {\ }}n}$
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

Geschichte

Das h​eute als Satz v​on Wilson bekannte Resultat w​urde erstmals v​on Ibn al-Haytham entdeckt, a​ber schließlich n​ach John Wilson (einem Studenten d​es englischen Mathematikers Edward Waring) benannt, d​er es m​ehr als 700 Jahre später wiederentdeckte. Waring veröffentlichte diesen Satz i​m Jahr 1770, obwohl w​eder er n​och Wilson e​inen Beweis erbringen konnten. Lagrange g​ab den ersten Beweis 1773.

Nach Dietrich Mahnke besteht Grund zur Annahme, dass 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.“

Verallgemeinerungen

Es g​ilt 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 d​es Satzes v​on 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 v​on Wilson i​st ein Spezialfall e​ines allgemeinen Satzes a​us der Theorie d​er endlichen Körper zugrunde, d​er sich w​ie folgt angeben lässt:[3]

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 v​on Fischer/Sacher folgend k​ann man w​ie folgt argumentieren:[4]

Die 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 i​st 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 g​ilt 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[5] (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

• 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. Gerd Fischer, Reinhard Sacher: Einführung in die Algebra. 1978, S. 162
4. 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).
5. Eric W. Weisstein: Wilson Quotient. In: MathWorld (englisch).