Registrieren Passwort vergessen?

Satz von Wilson

20. Okt 2008, 16:37

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.

Inhaltsverzeichnis

[Bearbeiten] Satz

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

Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren:

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

Umgekehrt kann man mit dem Satz auch schließen: Ist n \geq 2 eine beliebige natürliche Zahl, so gilt

(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 n > 4 und (n − 1)! nicht durch n teilbar, so ist n eine Primzahl. Ist (n − 1)! aber durch n teilbar, so erhält man aus dem Satz von Wilson die Information, dass n zusammengesetzt ist, ohne eine konkrete Faktorisierung n = ab mit a,b\ne1 zu kennen. Allerdings ist der Rechenaufwand für die Fakultät nicht geringer als Probedivisionen.

[Bearbeiten] 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. Es besteht Grund zur Annahme, dass Leibniz ein Jahrhundert zuvor von diesem Resultat wusste, es aber niemals publizierte.

[Bearbeiten] Verallgemeinerungen

Es gilt allgemein:

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

Eine leichte Verallgemeinerung des Satzes von Wilson lautet:

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

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

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

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

[Bearbeiten] Verwandte Begriffe

Primzahlen p, bei denen (p − 1)! + 1 sogar durch p2 teilbar ist, heißen Wilson-Primzahlen.

[Bearbeiten] Einzelnachweise

[Bearbeiten] Weblinks

Von „http://de.wikipedia.org/wiki/Satz_von_Wilson“
Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.
In Kooperation mit Lycos Europe Network