imported>Kompetenter: linkfix

2025-09-15T19:45:28Z

linkfix

Neue Seite

Der '''Satz von Wilson''' (benannt nach [[John Wilson (Mathematiker, 1741)|John Wilson]]) ist ein [[Satz (Mathematik)|mathematischer Satz]] aus der [[Zahlentheorie]]. Er macht [[Teilbarkeit]]saussagen zu den [[natürliche Zahl|natürlichen]] bzw. [[Ganze Zahl|ganzen Zahlen]] und wird deswegen auch der [[Elementare Zahlentheorie|elementaren Zahlentheorie]] zugeordnet, mit deren Methoden er auch bewiesen werden kann.

== Aussage ==

Der Satz von Wilson besagt: Eine natürliche Zahl <math>p\geq 2</math> ist genau dann eine [[Primzahl]], wenn <math>(p-1)! + 1</math> durch <math>p</math> teilbar ist. Dabei bezeichnet <math>(p-1)!</math> das [[Produkt (Mathematik)|Produkt]] <math>1\cdot2\cdot3\cdots (p-1)</math>.

Mit Hilfe des Begriffes der [[Kongruenz (Zahlentheorie)|Kongruenz]] kann man den Satz auch so formulieren: Ist <math>p\geq 2</math> eine natürliche Zahl, so gilt
: <math>(p-1)!\equiv-1 \pmod p \Longleftrightarrow p \ \mathrm{ist} \ \mathrm{prim.}</math>

Umgekehrt kann man mit dem Satz auch schließen: Sei <math>n\geq 2</math> eine natürliche Zahl, so gilt
: <math>(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}</math>
Ist also <math>n>4</math> und <math>(n-1)!</math> nicht durch <math>n</math> teilbar, so ist <math>n</math> eine Primzahl. Ist <math>(n-1)!</math> aber durch <math>n</math> teilbar, so erhält man aus dem Satz von Wilson die Information, dass <math>n</math> zusammengesetzt ist, ohne eine konkrete Faktorisierung <math>n=ab</math> mit <math>a,b\ne1</math> zu kennen. Allerdings ist der Rechenaufwand für die Fakultät nicht geringer als [[Probedivision]]en.

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

=== Anmerkungen ===
* Für jede natürliche Zahl <math>n \geq 2</math> ist jede der beiden Kongruenzen <math>(n-2)! \equiv 1 \pmod n</math> und <math>(n-1)! \equiv -1 \pmod n</math> 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 <math>-1</math>, indem man berücksichtigt, dass für <math>n \in \mathbb N</math> und <math>n \geq 2</math> stets die Kongruenzen <math>n-1 \equiv -1 \pmod n</math> und <math>(n-1) \cdot (-1) \equiv (-1)^2 \equiv 1 \pmod n</math> gelten. Der Satz von Wilson ist also gleichwertig zu der bei Sierpiński<ref>{{Literatur
|Autor=[[Wacław Sierpiński]]
|Titel=Elementary Theory of Numbers
|Reihe=North-Holland Mathematical Library
|BandReihe=31
|Auflage=2. überarbeitete und erweiterte
|Verlag=North-Holland (u. a.)
|Ort=Amsterdam (u. a.)
|Datum=1988
|ISBN=0-444-86662-0
|Online=[http://ams.math.uni-bielefeld.de/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Sierpinski&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=3&mx-pid=930670 MR0930670]}}</ref> als „Leibniz’ Theorem“ bezeichneten Formulierung
:: ''Eine [[natürliche Zahl]] <math>n \geq 2</math> ist eine [[Primzahl]] [[dann und nur dann]], wenn sie die [[Kongruenz (Zahlentheorie)|Kongruenz]]''
::: <math>(n-2)! \equiv 1 \pmod n</math>
:: ''erfüllt.''

* Von Fischer/Sacher – wie auch von anderen Autoren – wird als Satz von Wilson lediglich die Kongruenzaussage für [[Primzahl]]en <math>p \in \N</math> 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 <span style="background:#FFC0CB">pink</span>. Und wenn ''n'' eine zusammengesetzte Zahl ist, dann ist die Hintergrundfarbe <span style="background:#98FB98">hellgrün</span>.
{| class="wikitable" style="text-align:right"
|+ Tabelle der Rest modulo ''n''
|-
! <math>n</math> !! <math>(n-1)!</math> !! <math>(n-1)!\ \bmod\ n</math>
|- style="background:#FFC0CB"
| 2 || 1 || 1
|- style="background:#FFC0CB"
| 3 || 2 || 2
|- style="background:#98FB98"
| 4 || 6 || 2
|- style="background:#FFC0CB"
| 5 || 24 || 4
|- style="background:#98FB98"
| 6 || 120 || 0
|- style="background:#FFC0CB"
| 7 || 720 || 6
|- style="background:#98FB98"
| 8 || 5040 || 0
|- style="background:#98FB98"
| 9 || 40320 || 0
|- style="background:#98FB98"
| 10 || 362880 || 0
|- style="background:#FFC0CB"
| 11 || 3628800 || 10
|- style="background:#98FB98"
| 12 || 39916800 || 0
|- style="background:#FFC0CB"
| 13 || 479001600 || 12
|- style="background:#98FB98"
| 14 || 6227020800 || 0
|- style="background:#98FB98"
| 15 || 87178291200 || 0
|- style="background:#98FB98"
| 16 || 1307674368000 || 0
|- style="background:#FFC0CB"
| 17 || 20922789888000 || 16
|- style="background:#98FB98"
| 18 || 355687428096000 || 0
|- style="background:#FFC0CB"
| 19 || 6402373705728000 || 18
|- style="background:#98FB98"
| 20 || 121645100408832000 || 0
|- style="background:#98FB98"
| 21 || 2432902008176640000 || 0
|- style="background:#98FB98"
| 22 || 51090942171709440000 || 0
|- style="background:#FFC0CB"
| 23 || 1124000727777607680000 || 22
|- style="background:#98FB98"
| 24 || 25852016738884976640000 || 0
|- style="background:#98FB98"
| 25 || 620448401733239439360000 || 0
|- style="background:#98FB98"
| 26 || 15511210043330985984000000 || 0
|- style="background:#98FB98"
| 27 || 403291461126605635584000000 || 0
|- style="background:#98FB98"
| 28 || 10888869450418352160768000000 || 0
|- style="background:#FFC0CB"
| 29 || 304888344611713860501504000000 || 28
|- style="background:#98FB98"
| 30 || 8841761993739701954543616000000 || 0
|}

== Geschichte ==

Das heute als Satz von Wilson bekannte Resultat wurde erstmals von [[Alhazen|Ibn al-Haytham]] entdeckt, aber schließlich nach [[John Wilson (Mathematiker, 1741)|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 [[Kleiner Satz von Fermat|Kleinen Satz von Fermat]] und erwähnte auch die für Primzahlen <math>p</math> zum Satz von Wilson äquivalente (und von Sierpiński als „Leibniz’ Theorem“ bezeichnete) Tatsache, dass <math>(p-2)! \equiv 1 \pmod p</math> 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“<ref>Dietrich Mahnke: "Leibniz auf der Suche nach einer allgemeinen Primzahlgleichung." Bibl. Math. 13 (1912-13), 29–61.</ref> 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 <math> n </math> das Produkt von 2 mit einer Primzahl, so gilt auch:

:<math> \varphi(n)! \equiv \varphi(n) \mod{n} </math>

:Ansonsten ist <math> \varphi(n)! </math> kongruent zu Null.

:<math> \varphi</math> 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:

:<math>p</math> ist genau dann eine Primzahl, wenn die Summe <math>s=\sum_{k=1}^{p-3} k \cdot k!</math> durch <math>p</math> teilbar ist.

:''Beweis:''

::<math>s=1 \cdot 1! + 2 \cdot 2! + ... + (p-3) \cdot (p-3)!</math>

::Wegen <math>k \cdot k!=(k+1-1) \cdot k!=(k+1)!-k!</math> folgt:

::<math>s=(2!-1!) + (3!-2!) + (4!-3!) + ... + ((p-2)!-(p-3)!)=(p-2)!-1</math>

::Es gilt folgende Äquivalenzkette:

::<math>s=(p-2)!-1 | \cdot (p-1)</math>

::<math>\Leftrightarrow (p-1) \cdot s = (p-1)!-(p-1) | + p</math>

::<math>\Leftrightarrow (p-1) \cdot s + p= (p-1)!+1</math> ''(1)''

::Nach dem Satz von Wilson ist <math>p</math> genau dann eine Primzahl, wenn <math>(p-1)! + 1</math> durch <math>p</math> teilbar ist.

::Nach ''(1)'' ist demnach <math>p</math> genau dann eine Primzahl, wenn <math>(p-1)\cdot s + p</math> durch <math>p</math> teilbar ist, was wiederum gleichbedeutend damit ist, dass <math>(p-1)\cdot s</math> durch <math>p</math> teilbar ist.

::Da <math>p-1</math> und <math>p</math> teilerfremd sind, ist die letzte Aussage äquivalent dazu, dass <math>p</math> die Summe <math>s</math> teilt, [[Quod erat demonstrandum|was zu beweisen war]].<ref>[[Ross Honsberger]]: ''Gitter - Reste - Würfel'' [[Vieweg Verlag|Friedrich Vieweg & Sohn Verlagsgesellschaft mbH]], [[Braunschweig]] 1984, ISBN 978-3-528-08476-9, Seiten 34 und 35</ref><ref>Douglas Lind, Kenneth Kramer, Steven Minsker: ''Problem E 1702'', [[American Mathematical Monthly]], [[Los Angeles]], ([[Kalifornien]]) (1965)</ref>

== Verallgemeinerungen ==

Es gilt allgemein:

: <math>\prod_{\begin{matrix} 1 \le 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. </math>

Eine leichte Verallgemeinerung des Satzes von Wilson lautet:

Eine Zahl <math>p\in \mathbb{N}</math> ist genau dann Primzahl, wenn für alle <math>1\leq n\leq p</math>

: <math>(n-1)!(p-n)!\equiv (-1)^n\ \mathrm{mod}\ p</math>

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

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

== Körpertheoretische Formulierung ==

=== Allgemeiner Satz ===
Der Satz von Wilson ist ein Spezialfall eines allgemeinen Satzes aus der Theorie der [[Endlicher Körper|endlichen Körper]], der sich wie folgt angeben lässt:<ref name="GF-RS-0001">Gerd Fischer, Reinhard Sacher: ''Einführung in die Algebra.'' 1978, S. 162</ref>
: ''Ist <math>K</math> ein endlicher Körper und <math>K^{*}</math> seine [[Einheitengruppe]],''
: ''so ist stets die [[Gleichung]]''
:: <math>\prod\limits_{a \in K^{*} } {a} = -1</math>
: ''erfüllt.''

=== Beweis des allgemeinen Satzes ===
Der Darstellung von [[Gerd Fischer (Mathematiker)|Fischer]]/Sacher folgend kann man wie folgt argumentieren:<ref> {{Literatur
|Autor=[[Gerd Fischer (Mathematiker)|Gerd Fischer]], Reinhard Sacher
|Titel=Einführung in die Algebra
|Reihe=Teubner Studienbücher: Mathematik
|Auflage=2. überarbeitete
|Verlag=[[B. G. Teubner]]
|Ort=Stuttgart
|Datum=1978
|ISBN=3-519-12053-4
|Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=AUCN&pg7=ALLF&pg8=ET&review_format=html&s4=fischer&s5=Algebra&s6=sacher&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=1&mx-pid=492996 MR0492996]}} </ref>

Die in <math>K^{*}</math> gelegene [[Teilmenge]]
: <math>M:= \{a \in K^{*} \mid a=a^{-1} \} = \{a \in K^{*} \mid a^2=1 \} = \{a \in K^{*} \mid a^2-1 = 0 \}</math>

ist die [[Nullstellenmenge]] des [[Polynomring|Polynoms]] <math> X^2-1 \in K[X]</math> und wegen <math> (X-1)(X+1) = X^2-1</math> gilt
: <math>M = \{ 1,-1 \}</math>.

Andererseits ist offenbar
: <math>\prod\limits_{a \in K^{*} } {a} = \prod\limits_{a \in M } {a} </math>,

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

Also gilt die behauptete Gleichung.

== Verwandte Begriffe ==

Das nur für Primzahlen <math>p</math> ganzzahlige Ergebnis der Division
: <math>\frac{(p-1)! + 1}{p}</math>
wird als ''Wilson-Quotient'' <math>W(p)</math> bezeichnet<ref>{{MathWorld |id=WilsonQuotient |title=Wilson Quotient}}</ref> ({{OEIS|A007619}}).

Primzahlen <math>p</math>, bei denen <math>(p-1)!+1</math> sogar durch <math>p^2</math> teilbar ist, heißen [[Wilson-Primzahl]]en.

Beispiel: 13 ist Wilson-Primzahl; denn <math>(13-1)! + 1 = 13^2 \cdot 2\,834\,329 </math>.

== Weblinks ==
{{Wikibooks|Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Satz von Wilson|Beweis zum Satz von Wilson}}
* {{MathWorld |id=WilsonsTheorem |title=Wilson’s Theorem}}

== Einzelnachweise ==
<references />

[[Kategorie:Satz (Zahlentheorie)|Wilson]]

Satz von Wilson - Versionsgeschichte

imported>Kompetenter: linkfix