Twierdzenie Wilsona

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

${\displaystyle (p-1)!+1}$

jest podzielna przez ${\displaystyle p}$^[1][2].

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)^{[potrzebny przypis]}.

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

${\displaystyle x^{2}=1.}$

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

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

W ciele iloczyn niezerowych czynników jest niezerowy. Więc jedynymi rozwiązaniami powyższego równania są ${\displaystyle x=1}$ oraz ${\displaystyle x=-1}$ (w ciele ${\displaystyle \mathbb {Z} _{p},}$ dla ${\displaystyle p}$ różnego od 2, zachodzi nierówność ${\displaystyle -1\neq 1}$). Wynika stąd, że jedynymi elementami ciała ${\displaystyle \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 ${\displaystyle \{x,y\}}$ o iloczynie ${\displaystyle x\cdot y=1,}$ gdzie ${\displaystyle 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:

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

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

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

czyli ${\displaystyle (p-1)!+1}$ jest podzielna przez ${\displaystyle p.}$

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

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

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

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

więc

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

Tak więc

${\displaystyle (p-1)!\ \not \equiv \ -1\mod p}$

i liczba ${\displaystyle (p-1)!+1}$ nie jest podzielna przez ${\displaystyle p.}$

Uogólnienie

Istnieje uogólnienie twierdzenia Wilsona, autorstwa Gaussa:

${\displaystyle \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 ${\displaystyle p}$ jest liczbą pierwszą większą od 2.

Dla ${\displaystyle m=2}$ zachodzi

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

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

Przypisy