Der Satz von Wilson benannt nach John Wilson ist ein mathematischer Satz aus der Zahlentheorie Er macht Teilbarkeitsaussagen zu den naturlichen bzw ganzen Zahlen und wird deswegen auch der elementaren Zahlentheorie zugeordnet mit deren Methoden er auch bewiesen werden kann Inhaltsverzeichnis 1 Aussage 1 1 Direkter Beweis 1 2 Anmerkungen 2 Beispiele 3 Geschichte 4 Korollare 5 Verallgemeinerungen 6 Korpertheoretische Formulierung 6 1 Allgemeiner Satz 6 2 Beweis des allgemeinen Satzes 7 Verwandte Begriffe 8 Weblinks 9 EinzelnachweiseAussage BearbeitenDer Satz von Wilson besagt Eine naturliche Zahl p 2 displaystyle p geq 2 nbsp ist genau dann eine Primzahl wenn p 1 1 displaystyle p 1 1 nbsp durch p displaystyle p nbsp teilbar ist Dabei bezeichnet p 1 displaystyle p 1 nbsp das Produkt 1 2 3 p 1 displaystyle 1 cdot 2 cdot 3 cdots p 1 nbsp Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren Ist p 2 displaystyle p geq 2 nbsp eine naturliche Zahl so gilt p 1 1 mod p p i s t p r i m displaystyle p 1 equiv 1 pmod p Longleftrightarrow p mathrm ist mathrm prim nbsp Umgekehrt kann man mit dem Satz auch schliessen Sei n 2 displaystyle n geq 2 nbsp eine naturliche Zahl so gilt n 1 n 1 mod n f a l l s n P r i m z a h l 2 mod n f a l l s n 4 0 mod n s o n s t displaystyle n 1 equiv begin cases n 1 pmod n amp mathrm falls n mathrm Primzahl 2 pmod n amp mathrm falls n 4 0 pmod n amp mathrm sonst end cases nbsp Ist also n gt 4 displaystyle n gt 4 nbsp und n 1 displaystyle n 1 nbsp nicht durch n displaystyle n nbsp teilbar so ist n displaystyle n nbsp eine Primzahl Ist n 1 displaystyle n 1 nbsp aber durch n displaystyle n nbsp teilbar so erhalt man aus dem Satz von Wilson die Information dass n displaystyle n nbsp zusammengesetzt ist ohne eine konkrete Faktorisierung n a b displaystyle n ab nbsp mit a b 1 displaystyle a b neq 1 nbsp zu kennen Allerdings ist der Rechenaufwand fur die Fakultat nicht geringer als Probedivisionen Direkter Beweis Bearbeiten Ist p displaystyle p nbsp eine Primzahl so ist der Restklassenring Z p 0 p 1 displaystyle mathbb Z p overline 0 ldots overline p 1 nbsp ein Korper in dem 1 displaystyle overline 1 nbsp und p 1 displaystyle overline p 1 nbsp die einzigen zu sich selbst inversen Elemente sind Daher kommt im Produkt 2 3 p 2 displaystyle overline 2 cdot overline 3 cdot ldots cdot overline p 2 nbsp jeder Faktor zusammen mit seinem inversen Element vor weshalb das Produkt gleich 1 displaystyle overline 1 nbsp ist Das bedeutet aber gerade p 2 1 mod p displaystyle p 2 equiv 1 pmod p nbsp woraus p 1 1 mod p displaystyle p 1 equiv 1 pmod p nbsp folgt Ist umgekehrt n gt 4 displaystyle n gt 4 nbsp keine Primzahl so gibt es Faktoren 1 lt a b n 2 displaystyle 1 lt a b leq n 2 nbsp mit n a b displaystyle n a cdot b nbsp Daher ist a b 0 displaystyle overline a cdot overline b overline 0 nbsp und a 2 b 0 displaystyle overline a cdot overline 2b overline 0 nbsp jedenfalls gibt es im Produkt 2 3 n 2 displaystyle overline 2 cdot overline 3 cdot ldots cdot overline n 2 nbsp zwei Faktoren deren Produkt 0 displaystyle overline 0 nbsp ist weshalb das gesamte Produkt in Z n displaystyle mathbb Z n nbsp verschwinden muss Das bedeutet aber n 2 0 mod n displaystyle n 2 equiv 0 pmod n nbsp und erst recht n 1 0 mod n displaystyle n 1 equiv 0 pmod n nbsp Anmerkungen Bearbeiten Fur jede naturliche Zahl n 2 displaystyle n geq 2 nbsp ist jede der beiden Kongruenzen n 2 1 mod n displaystyle n 2 equiv 1 pmod n nbsp und n 1 1 mod n displaystyle n 1 equiv 1 pmod n nbsp genau dann erfullt wenn die jeweils andere erfullt ist Man gewinnt dabei die eine aus der anderen und vice versa durch Rechtsmultiplikation mit 1 displaystyle 1 nbsp indem man berucksichtigt dass fur n N displaystyle n in N nbsp und n 2 displaystyle n geq 2 nbsp stets die Kongruenzen n 1 1 mod n displaystyle n 1 equiv 1 pmod n nbsp und n 1 1 1 2 1 mod n displaystyle n 1 cdot 1 equiv 1 2 equiv 1 pmod n nbsp gelten Der Satz von Wilson ist also gleichwertig zu der bei Sierpinski 1 als Leibniz Theorem bezeichneten FormulierungEine naturliche Zahl n 2 displaystyle n geq 2 nbsp ist eine Primzahl dann und nur dann wenn sie die Kongruenz n 2 1 mod n displaystyle n 2 equiv 1 pmod n nbsp dd erfullt dd Von Fischer Sacher wie auch von anderen Autoren wird als Satz von Wilson lediglich die Kongruenzaussage fur Primzahlen p N displaystyle p in mathbb N nbsp zitiert Beispiele BearbeitenDie 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 hellgrun Tabelle der Rest modulo n n displaystyle n nbsp n 1 displaystyle n 1 nbsp n 1 mod n displaystyle n 1 bmod n nbsp 2 1 13 2 24 6 25 24 46 120 07 720 68 5040 09 40320 010 362880 011 3628800 1012 39916800 013 479001600 1214 6227020800 015 87178291200 016 1307674368000 017 20922789888000 1618 355687428096000 019 6402373705728000 1820 121645100408832000 021 2432902008176640000 022 51090942171709440000 023 1124000727777607680000 2224 25852016738884976640000 025 620448401733239439360000 026 15511210043330985984000000 027 403291461126605635584000000 028 10888869450418352160768000000 029 304888344611713860501504000000 2830 8841761993739701954543616000000 0Geschichte BearbeitenDas heute als Satz von Wilson bekannte Resultat wurde erstmals von Ibn al Haytham entdeckt aber schliesslich nach John Wilson einem Studenten des englischen Mathematikers Edward Waring benannt der es mehr als 700 Jahre spater wiederentdeckte Waring veroffentlichte 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 erwahnte auch die fur Primzahlen p displaystyle p nbsp zum Satz von Wilson aquivalente und von Sierpinski als Leibniz Theorem bezeichnete Tatsache dass p 2 1 mod p displaystyle p 2 equiv 1 pmod p nbsp ist wobei er falschlich behauptete dass der Rest 1 oder 1 sein konnte Mahnke fuhrt 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 veroffentlicht und Lagrange an der angegebenen Stelle ihn zuerst bewiesen hat Leibniz hat namlich 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 Wurde man die erste Kongruenz mit p 1 multiplizieren so wurde der bekannte Wilsonsche Satz folgen Leibniz hat nun seinen induktiv gefundenen Satz noch bei der nachsten Primzahl p 17 nachgepruft sich dabei aber verrechnet Er gibt namlich an 11 16 15 16 16 1 mod 17 wahrend in Wirklichkeit 11 1 15 1 16 16 mod 17 ist Durch diesen Rechenfehler ist er veranlasst worden seinen richtigen Satz abzuandern 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 wahrend in Wirklichkeit 15 1 mod 17 ist So erklart sich dieser falsche Zusatz der Vacca unverstandlich war Korollare BearbeitenIst n displaystyle n nbsp das Produkt von 2 mit einer Primzahl so gilt auch f n f n mod n displaystyle varphi n equiv varphi n mod n nbsp Ansonsten ist das Ergebnis kongruent zu Null f displaystyle varphi nbsp bezeichnet dabei die eulersche Phi FunktionEin weiteres Korollar bezieht sich auf eine Summe von Produkten in denen jeweils eine Fakultat als Faktor enthalten ist p displaystyle p nbsp ist genau dann eine Primzahl wenn die Summe s k 1 p 3 k k displaystyle s sum k 1 p 3 k cdot k nbsp durch p displaystyle p nbsp teilbar ist Beweis s 1 1 2 2 p 3 p 3 displaystyle s 1 cdot 1 2 cdot 2 p 3 cdot p 3 nbsp dd Wegen k k k 1 1 k k 1 k displaystyle k cdot k k 1 1 cdot k k 1 k nbsp folgt dd s 2 1 3 2 4 3 p 2 p 3 p 2 1 displaystyle s 2 1 3 2 4 3 p 2 p 3 p 2 1 nbsp dd Es gilt folgende Aquivalenzkette dd s p 2 1 p 1 displaystyle s p 2 1 cdot p 1 nbsp dd p 1 s p 1 p 1 p displaystyle Leftrightarrow p 1 cdot s p 1 p 1 p nbsp dd p 1 s p p 1 1 displaystyle Leftrightarrow p 1 cdot s p p 1 1 nbsp 1 dd Nach dem Satz von Wilson ist p displaystyle p nbsp genau dann eine Primzahl wenn p 1 1 displaystyle p 1 1 nbsp durch p displaystyle p nbsp teilbar ist dd Nach 1 ist demnach p displaystyle p nbsp genau dann eine Primzahl wenn p 1 s p displaystyle p 1 cdot s p nbsp durch p displaystyle p nbsp teilbar ist was wiederum gleichbedeutend damit ist dass p 1 s displaystyle p 1 cdot s nbsp durch p displaystyle p nbsp teilbar ist dd Da p 1 displaystyle p 1 nbsp und p displaystyle p nbsp teilerfremd sind ist die letzte Aussage aquivalent dazu dass p displaystyle p nbsp die Summe s displaystyle s nbsp teilt was zu beweisen war 3 4 dd Verallgemeinerungen BearbeitenEs gilt allgemein 1 a lt m a m 1 a 1 mod m wenn m 4 p a 2 p a a N 1 mod m sonst displaystyle prod begin matrix 1 leq a lt m a m 1 end matrix a equiv left begin matrix 1 mbox mod m amp mbox wenn m 4 p alpha 2p alpha alpha in mathbb N 1 mbox mod m amp mbox sonst end matrix right nbsp Eine leichte Verallgemeinerung des Satzes von Wilson lautet Eine Zahl p N displaystyle p in mathbb N nbsp ist genau dann Primzahl wenn fur alle 1 n p displaystyle 1 leq n leq p nbsp n 1 p n 1 n m o d p displaystyle n 1 p n equiv 1 n mathrm mod p nbsp gilt Dieser Satz lasst sich leicht mit vollstandiger Induktion nach n displaystyle n nbsp und mit dem Satz von Wilson beweisen Fur n 1 displaystyle n 1 nbsp oder n p displaystyle n p nbsp ergibt sich der Satz von Wilson Setzt man hier n p 1 2 displaystyle n frac p 1 2 nbsp so ergibt sich p N displaystyle p in mathbb N nbsp mit p gt 2 displaystyle p gt 2 nbsp und ungerade ist genau dann Primzahl wenn p 1 2 2 1 p 1 2 m o d p displaystyle left left frac p 1 2 right right 2 equiv 1 frac p 1 2 mathrm mod p nbsp Korpertheoretische Formulierung BearbeitenAllgemeiner Satz Bearbeiten Der Satz von Wilson ist ein Spezialfall eines allgemeinen Satzes aus der Theorie der endlichen Korper der sich wie folgt angeben lasst 5 Ist K displaystyle K nbsp ein endlicher Korper und K displaystyle K nbsp seine Einheitengruppe so ist stets die Gleichung a K a 1 displaystyle prod limits a in K a 1 nbsp dd erfullt Beweis des allgemeinen Satzes Bearbeiten Der Darstellung von Fischer Sacher folgend kann man wie folgt argumentieren 6 Die in K displaystyle K nbsp gelegene Teilmenge M a K a a 1 a K a 2 1 a K a 2 1 0 displaystyle M a in K mid a a 1 a in K mid a 2 1 a in K mid a 2 1 0 nbsp ist die Nullstellenmenge des Polynoms X 2 1 K X displaystyle X 2 1 in K X nbsp und wegen X 1 X 1 X 2 1 displaystyle X 1 X 1 X 2 1 nbsp gilt M 1 1 displaystyle M 1 1 nbsp Andererseits ist offenbar a K a a M a displaystyle prod limits a in K a prod limits a in M a nbsp denn jedes Korperelement a K M displaystyle a in K setminus M nbsp liefert in dem Produkt zusammen mit seinem Inversen stets den Beitrag 1 displaystyle 1 nbsp Also gilt die behauptete Gleichung Verwandte Begriffe BearbeitenDas nur fur Primzahlen p displaystyle p nbsp ganzzahlige Ergebnis der Division p 1 1 p displaystyle frac p 1 1 p nbsp wird als Wilson Quotient W p displaystyle W p nbsp bezeichnet 7 Folge A007619 in OEIS Primzahlen p displaystyle p nbsp bei denen p 1 1 displaystyle p 1 1 nbsp sogar durch p 2 displaystyle p 2 nbsp teilbar ist heissen Wilson Primzahlen Beispiel 13 ist Wilson Primzahl denn 13 1 1 13 2 2 834 329 displaystyle 13 1 1 13 2 cdot 2 834 329 nbsp Weblinks Bearbeiten nbsp Wikibooks Beweis zum Satz von Wilson Lern und Lehrmaterialien Eric W Weisstein Wilson s Theorem In MathWorld englisch Einzelnachweise Bearbeiten Waclaw Sierpinski Elementary Theory of Numbers North Holland Mathematical Library Band 31 2 uberarbeitete und erweiterte Auflage North Holland u a Amsterdam u a 1988 ISBN 0 444 86662 0 MR0930670 Dietrich Mahnke Leibniz auf der Suche nach einer allgemeinen Primzahlgleichung Bibl Math 13 1912 13 29 61 Ross Honsberger Gitter Reste Wurfel Friedrich Vieweg amp Sohn Verlagsgesellschaft mbH Braunschweig 1984 ISBN 978 3 528 08476 9 Seiten 34 und 35 Douglas Lind Kenneth Kramer Steven Minsker Problem E 1702 American Mathematical Monthly Los Angeles Kalifornien 1965 Gerd Fischer Reinhard Sacher Einfuhrung in die Algebra 1978 S 162 Gerd Fischer Reinhard Sacher Einfuhrung in die Algebra Teubner Studienbucher Mathematik 2 uberarbeitete Auflage B G Teubner Stuttgart 1978 ISBN 3 519 12053 4 MR0492996 Eric W Weisstein Wilson Quotient In MathWorld englisch Abgerufen von https de wikipedia org w index php title Satz von Wilson amp oldid 237554453
