Satz von Wilson

aus Wikipedia, der freien Enzyklopädie

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.

Satz

Der Satz von Wilson lautet: Sei eine natürliche Zahl. Dann ist genau dann eine Primzahl, wenn durch teilbar ist. Dabei bezeichnet die Fakultät, also das Produkt .

Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren: Sei eine natürliche Zahl, so gilt

Umgekehrt kann man mit dem Satz auch schließen: Sei eine natürliche Zahl, so gilt

Ist also und nicht durch teilbar, so ist eine Primzahl. Ist aber durch teilbar, so erhält man aus dem Satz von Wilson die Information, dass zusammengesetzt ist, ohne eine konkrete Faktorisierung mit 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 eine Primzahl, so ist der Restklassenring ein Körper, in dem und die einzigen zu sich selbst inversen Elemente sind. Daher kommt im Produkt jeder Faktor zusammen mit seinem inversen Element vor, weshalb das Produkt gleich ist. Das bedeutet aber gerade , woraus folgt. Ist umgekehrt keine Primzahl, so gibt es Faktoren mit . Daher ist und , jedenfalls gibt es im Produkt zwei Faktoren, deren Produkt ist, weshalb das gesamte Produkt in verschwinden muss. Das bedeutet aber und erst recht .

Anmerkungen

  • Für jede natürliche Zahl ist jede der beiden Kongruenzen und 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 , indem man berücksichtigt, dass für und stets die Kongruenzen und gelten. Der Satz von Wilson ist also gleichwertig zu der bei Sierpiński[1] als "Leibniz' Theorem" bezeichneten Formulierung
Eine natürliche Zahl ist eine Primzahl dann und nur dann, wenn sie die Kongruenz
erfüllt.
  • Von Fischer/Sacher – wie auch von anderen Autoren – wird als Satz von Wilson lediglich die Kongruenzaussage für Primzahlen 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.

Tabelle der Rest modulo 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 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. Lagrange gab 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 zum Satz von Wilson äquivalente (und von Sierpiński als „Leibniz’ Theorem“ bezeichnete) Tatsache, dass 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.

Korollar

Ist das Produkt von 2 mit einer Primzahl, so gilt auch:

Ansonsten ist das Ergebnis kongruent zu Null.

bezeichnet dabei die eulersche Phi-Funktion

Verallgemeinerungen

Es gilt allgemein:

Eine leichte Verallgemeinerung des Satzes von Wilson lautet:

Eine Zahl ist genau dann Primzahl, wenn für alle

gilt. Dieser Satz lässt sich leicht mit vollständiger Induktion nach und mit dem Satz von Wilson beweisen. Für oder ergibt sich der Satz von Wilson. Setzt man hier , so ergibt sich:

mit und ungerade ist genau dann Primzahl, wenn .

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:[3]

Ist ein endlicher Körper und seine Einheitengruppe,
so ist stets die Gleichung
erfüllt.

Beweis des allgemeinen Satzes

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

Die die in gelegene Teilmenge

ist die Nullstellenmenge des Polynoms und wegen gilt

.

Andererseits ist offenbar

,

denn jedes Körperelement liefert in dem Produkt zusammen mit seinem Inversen stets den Beitrag .

Also gilt die behauptete Gleichung.

Verwandte Begriffe

Das nur für Primzahlen ganzzahlige Ergebnis der Division

wird als Wilson-Quotient bezeichnet[5] (Folge A007619 in OEIS).

Primzahlen , bei denen sogar durch teilbar ist, heißen Wilson-Primzahlen.

Beispiel: 13 ist Wilson-Primzahl; denn .

Weblinks

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

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).