Twierdzenie Wilsona

Twierdzenie Wilsona – twierdzenie w teorii liczb. Mówi ono, że liczba naturalna $p>1$ jest liczbą pierwszą wtedy i tylko wtedy, gdy liczba

$(p-1)!+1$

jest podzielna przez $p$.

Twierdzenie zostało odkryte przez Johna Wilsona, będącego studentem Edwarda Waringa. Jednak żaden z nich nie był w stanie go udowodnić. Dopiero w 1773 roku Lagrange dał przekonujący dowód. Istnieją również argumenty mówiące, że to Leibniz był pierwszym, który udowodnił to twierdzenie (chociaż nie opublikował dowodu).

Twierdzenie to daje potencjalną możliwość sprawdzenia dla każdej liczby naturalnej, czy jest pierwsza. Ponieważ nie są znane efektywne algorytmy obliczania silni, twierdzenia tego nie da się łatwo stosować w badaniu pierwszości liczb.

Dowód

Najpierw załóżmy, że $p$ jest liczbą pierwszą. Twierdzenie zachodzi dla $p=2$ oraz $p=3.$ Więc dodatkowo załóżmy, że $p>3.$ Klasy liczb całkowitych mod $p$ tworzą ciało $\mathbb {Z} _{p}.$ Rozpatrzmy w nim równanie:

$x^{2}=1.$

Ma ono te same rozwiązania co równanie $x^{2}-1=0,$ czyli

$(x-1)\cdot (x+1)=0.$

W ciele iloczyn niezerowych czynników jest niezerowy. Więc jedynymi rozwiązaniami powyższego równania są $x=1$ oraz $x=-1$ (w ciele $\mathbb {Z} _{p},$ dla $p$ różnego od 2, zachodzi nierówność $-1\neq 1$). Wynika stąd, że jedynymi elementami ciała $\mathbb {Z} _{p},$ które są odwrotne do siebie, są 1 i –1. Zatem zbiór pozostałych niezerowych elementów ciała rozpada się na rozłączne pary elementów $\{x,y\}$ o iloczynie $x\cdot y=1,$ gdzie $x\neq y.$ Stąd wnioskujemy iż iloczyn wszystkich, poza 1 oraz –1, niezerowych elementów ciała, jako iloczyn iloczynów takich par, wynosi 1, co oznacza, że:

$2\cdot \ldots \cdot (p-2)\equiv 1\mod p.$

Po przemnożeniu powyższej kongruencji przez $p-1,$ czyli przez $-1$ (co jest tym samym mod $p$), oraz po dopisaniu nieszkodliwego 1 po lewej, otrzymujemy:

$1\cdot \ldots \cdot (p-1)\equiv -1\mod p,$

czyli $(p-1)!+1$ jest podzielna przez $p.$

Wykażemy teraz twierdzenie przeciwne i w tym celu przypuśćmy, że $p$ jest złożoną liczbą naturalną. Wtedy istnieją takie dzielniki właściwe $a$ oraz $b$ liczby $p,$ że $a\cdot b=p.$ Wtedy $a\ |\ (p-1)!.$ Zatem

$a\cdot b\ |\ (p-1)!\cdot b$

i stąd (pamiętając, że $p=a\cdot b$)

$(p-1)!\cdot b\equiv \;0\mod p,$

więc

$(p-1)!\cdot b\not \equiv (-1)\cdot b\mod p.$

Tak więc

$(p-1)!\ \not \equiv \ -1\mod p$

i liczba $(p-1)!+1$ nie jest podzielna przez $p.$

Uogólnienie

Istnieje uogólnienie twierdzenia Wilsona, autorstwa Gaussa:

$\prod _{a=1 \atop \operatorname {NWD} (a,m)=1}^{m}\!\!a\ \equiv \ \left\{{\begin{matrix}-1\ ({\text{mod }}m)&{\text{gdy }}\ m=4,\;p^{\alpha },\;2p^{\alpha },\\\quad 1\ ({\text{mod }}m)&{\text{w innych wypadkach}},\end{matrix}}\right.$

gdzie $p$ jest liczbą pierwszą większą od 2.

Dla $m=2$ zachodzi

$-1\equiv 1({\text{mod }}2),$

więc równie dobrze można dodać $m=2$ do drugiej gałęzi wzoru.