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.

[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\ \mathrm{mod}\ n, \\ 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 = a b$ 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 weitere Verallgemeinerung des Satzes von Wilson wurde 2003 von Thomas Krakow bewiesen ^[1], nämlich die folgende:

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