Satz von Wilson
# Satz von Wilson

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.

## Aussage

Der Satz von Wilson besagt: Eine natürliche Zahl $p\geq 2$ ist genau dann eine Primzahl, wenn $(p-1)!+1$ durch $p$ teilbar ist. Dabei bezeichnet $(p-1)!$ das Produkt $1\cdot 2\cdot 3\cdots (p-1)$.
Mit Hilfe des Begriffes der Kongruenz kann man den Satz auch so formulieren: Ist $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\neq 1$ zu kennen. Allerdings ist der Rechenaufwand für die Fakultät nicht geringer als Probedivisionen.

### Direkter Beweis

Ist $p$ eine Primzahl, so ist der Restklassenring $\mathbb {Z} /(p)=\{{\overline {0}},\ldots ,{\overline {p-1}}\}$ ein Körper, in dem ${\overline {1}}$ und ${\overline {p-1}}$ die einzigen zu sich selbst inversen Elemente bezüglich der Multiplikation sind. Daher kommt im Produkt ${\overline {2}}\cdot {\overline {3}}\cdot \ldots \cdot {\overline {p-2}}$ jeder Faktor zusammen mit seinem inversen Element vor, weshalb das Produkt gleich ${\overline {1}}$ ist. Das bedeutet aber gerade $(p-2)!\equiv 1{\pmod {p}}$, woraus $(p-1)!\equiv -1{\pmod {p}}$ folgt. Ist umgekehrt $n>4$ keine Primzahl, so gibt es Faktoren $1<a,b\leq n-2$ mit $n=a\cdot b$. Daher ist ${\overline {a}}\cdot {\overline {b}}={\overline {0}}$ und ${\overline {a}}\cdot {\overline {2b}}={\overline {0}}$, jedenfalls gibt es im Produkt ${\overline {2}}\cdot {\overline {3}}\cdot \ldots \cdot {\overline {n-2}}$ zwei Faktoren, deren Produkt ${\overline {0}}$ ist, weshalb das gesamte Produkt in $\mathbb {Z} /(n)$ verschwinden muss. Das bedeutet aber $(n-2)!\equiv 0{\pmod {n}}$ und erst recht $(n-1)!\equiv 0{\pmod {n}}$.