Satz von Wilson

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Satz von Wilson (nach J. Wilson) ist ein Ergebnis des mathematischen Teilgebietes der elementaren Zahlentheorie.

Er besagt: Genau dann ist $p > 1$ eine Primzahl, wenn

$(p-1)! + 1 \,\!$

durch $p$ teilbar ist. Dabei bezeichnet $n!$ die Fakultät einer Zahl $n$ , also das Produkt $1\cdot2\cdot3\cdots n$ .

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

$(p-1)!\equiv-1\pmod p.$

Ist allgemein $n$ eine beliebige natürliche Zahl, so gilt

$(n-1)!\equiv\begin{cases}n-1, & \mathrm{falls}\ n\ \mathrm{Primzahl} \\ 2, & \mathrm{falls}\ n=4 \\ 0 & \mathrm{sonst}\end{cases}\quad\pmod n.$

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 = a b$ mit $a,b\ne1$ zu kennen. Allerdings ist der Rechenaufwand für die Fakultät nicht geringer als Probedivisionen.

Es existiert auch eine Umkehrung des Satzes von Wilson.

[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 weitere Verallgemeinerung des Satzes von Wilson wurde 2003 von Thomas Krakow bewiesen, die 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\mbox{mod }p$

gilt. Dieser Satz lässt sich leicht mit vollständiger Induktion nach n und den 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: