Satz von Wilson

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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: Sei p\geq 2 eine natürliche Zahl, so gilt

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

Umgekehrt kann man mit dem Satz auch schließen: Sei n\geq 2 eine 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.

Beispiele[Bearbeiten]

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
n (n-1)! (n-1)!\ \bmod\ 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[Bearbeiten]

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.

Verallgemeinerungen[Bearbeiten]

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} mit p>2 und ungerade ist genau dann Primzahl, wenn \left(\left( \frac{p-1}{2}\right)!\right)^2 \equiv (-1)^{\frac{p+1}{2}}\ \mathrm{mod}\ p.

Verwandte Begriffe[Bearbeiten]

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

Weblinks[Bearbeiten]