Twierdzenie Wilsona

Q: Czy twierdzenie działa w obie strony?

Tak - i to je wyróżnia. Reszta -1 z dzielenia (n-1)! przez n zachodzi dokładnie dla liczb pierwszych.

Q: Dlaczego n = 4 jest wyjątkiem?

Bo 4 = 2 · 2, a w iloczynie 3! = 1 · 2 · 3 dwójka występuje tylko raz - brakuje drugiego czynnika, który dopełniłby 4. Dla większych kwadratów liczb pierwszych problem znika, bo 2p mieści się poniżej p².

Q: Czym różni się od małego twierdzenia Fermata?

Twierdzenie Fermata daje warunek konieczny pierwszości (i dają się je oszukać liczbom Carmichaela), a twierdzenie Wilsona - warunek równoważny. Za to Fermata liczy się szybko, a Wilsona bardzo wolno.

Q: Co to są liczby pierwsze Wilsona?

Liczby pierwsze p, dla których p² dzieli (p-1)! + 1 (czyli warunek zachodzi „mocniej"). Znamy tylko trzy: 5, 13 oraz 563 - i nie wiadomo, czy jest ich nieskończenie wiele.

Liczba naturalna $p > 1$ jest pierwsza wtedy i tylko wtedy, gdy

$(p-1)! \equiv -1 \pmod{p},$

równoważnie: gdy $p$ dzieli liczbę $(p-1)! + 1$ .

Co mówi twierdzenie

Silnia $(p-1)! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1)$ to iloczyn wszystkich liczb mniejszych od $p$ . Twierdzenie Wilsona mówi, że reszta z dzielenia tego iloczynu przez $p$ rozstrzyga o pierwszości: dla liczb pierwszych wynosi zawsze $p - 1$ (czyli $-1$ ), a dla złożonych - nigdy.

To rzadka sytuacja. Większość kryteriów działa tylko w jedną stronę - jak małe twierdzenie Fermata, które dają się oszukać liczbom Carmichaela. Twierdzenie Wilsona jest równoważnością: nie ma liczb, które by je zwiodły.

Przykłady na liczbach

Dla $p = 5$ :

$4! = 24 = 5 \cdot 5 - 1 \quad\Longrightarrow\quad 24 \equiv -1 \pmod 5.$

Dla $p = 7$ :

$6! = 720 = 7 \cdot 103 - 1 \quad\Longrightarrow\quad 720 \equiv -1 \pmod 7.$

Dla $p = 11$ :

$10! = 3\,628\,800 = 11 \cdot 329\,891 - 1 \quad\Longrightarrow\quad 10! \equiv -1 \pmod{11}.$

A dla liczby złożonej $n = 9$ :

$8! = 40\,320 = 9 \cdot 4480 \quad\Longrightarrow\quad 8! \equiv 0 \pmod 9,$

czyli nie $-1$ - dokładnie tak, jak zapowiada twierdzenie.

Dowód

Pokaż dowódUkryj dowód

Dowodzimy implikacji „jeśli $p$ jest pierwsza, to $(p-1)! \equiv -1$ ”. Dla $p = 2$ sprawdzamy wprost: $1! = 1 \equiv -1 \pmod 2$ . Niech dalej $p \geq 3$ .

Krok 1. Każda liczba ma odwrotność. Dla $p$ pierwszej i $a \in \{1, 2, \ldots, p-1\}$ istnieje dokładnie jedna liczba $a^{-1}$ z tego samego zbioru, dla której

$a \cdot a^{-1} \equiv 1 \pmod p.$

Wynika to stąd, że $\mathrm{NWD}(a, p) = 1$ , więc równanie $ax \equiv 1$ ma rozwiązanie (daje je algorytm Euklidesa).

Krok 2. Kto jest swoją własną odwrotnością. Szukamy $a$ spełniających $a \equiv a^{-1}$ , czyli

$a^2 \equiv 1 \pmod p \quad\Longleftrightarrow\quad (a-1)(a+1) \equiv 0 \pmod p.$

Liczba pierwsza dzieląca iloczyn musi dzielić któryś czynnik, więc $a \equiv 1$ albo $a \equiv -1$ . W naszym zbiorze są to dokładnie dwie liczby: $1$ oraz $p - 1$ .

Krok 3. Resztę parujemy. Pozostałe $p - 3$ liczby dzielą się na pary $\{a, a^{-1}\}$ o iloczynie przystającym do $1$ . Par jest $\tfrac{p-3}{2}$ , a ich łączny iloczyn to $1$ .

Krok 4. Mnożymy wszystko.

$(p-1)! \equiv 1 \cdot 1 \cdot (p-1) \equiv -1 \pmod p. \qquad \blacksquare$

Przykład parowania dla $p = 11$ . Pary to $(2,6)$ , $(3,4)$ , $(5,9)$ , $(7,8)$ - bo $2 \cdot 6 = 12 \equiv 1$ , $3 \cdot 4 = 12 \equiv 1$ , $5 \cdot 9 = 45 \equiv 1$ oraz $7 \cdot 8 = 56 \equiv 1 \pmod{11}$ . Samotne zostają $1$ i $10$ , a $10 \equiv -1$ .

Twierdzenie odwrotne - też prawdziwe

Trzeba jeszcze pokazać, że dla liczby złożonej kongruencja nie zachodzi. Niech $n > 4$ będzie złożona.

Przypadek 1: $n = ab$ dla pewnych $1 < a < b < n$ . Oba czynniki występują wśród $1, 2, \ldots, n-1$ , więc ich iloczyn $n$ dzieli $(n-1)!$ :

$(n-1)! \equiv 0 \pmod n.$

Przypadek 2: $n = p^2$ dla liczby pierwszej $p \geq 3$ . W iloczynie $(n-1)!$ występują wtedy obie liczby $p$ oraz $2p$ (bo $2p < p^2$ dla $p \geq 3$ ), a ich iloczyn $2p^2$ dzieli się przez $n = p^2$ . Znowu $(n-1)! \equiv 0$ .

Jedyny wyjątek: $n = 4$ . Tutaj $3! = 6 \equiv 2 \pmod 4$ - ani $-1$ , ani $0$ . Dlatego w twierdzeniu odwrotnym zakłada się $n > 4$ .

Twierdzenie Wilsona jest więc pełnoprawnym kryterium pierwszości: reszta $-1$ oznacza liczbę pierwszą, każda inna - złożoną.

Dlaczego nie używa się go jako testu pierwszości

Skoro kryterium jest bezbłędne, dlaczego programy sprawdzające pierwszość go nie stosują? Bo policzenie $(n-1)! \bmod n$ wymaga około $n$ mnożeń. Dla liczby $300$ -cyfrowej, jakich używa RSA, byłoby to około $10^{300}$ operacji - nieporównanie więcej, niż zdąży wykonać jakikolwiek komputer.

Dla porównania: naiwne dzielenie próbne potrzebuje około $\sqrt{n}$ operacji, a test Millera-Rabina - kilkudziesięciu potęgowań modularnych. Twierdzenie Wilsona jest więc teoretycznie idealne i praktycznie bezużyteczne. To dobra lekcja o różnicy między tym, co rozstrzygalne, a tym, co obliczalne w rozsądnym czasie.

Gdzie się przydaje

W dowodach teoretycznych. Z twierdzenia Wilsona wynika, że dla liczby pierwszej $p \equiv 1 \pmod 4$ liczba $\left(\tfrac{p-1}{2}\right)!$ jest pierwiastkiem z $-1$ modulo $p$ . To kluczowy krok w dowodzie, że każda taka liczba pierwsza jest sumą dwóch kwadratów (np. $13 = 4 + 9$ ).
We „wzorach na liczby pierwsze”. Istnieją wzory generujące kolejne liczby pierwsze oparte na twierdzeniu Wilsona - efektowne, lecz bezużyteczne rachunkowo właśnie z powodu silni.
W zadaniach olimpijskich. Reszty z dzielenia silni to klasyka konkursów matematycznych.

Kto i kiedy

Twierdzenie znał już około 1000 roku arabski uczony Ibn al-Hajsam (Alhazen). Nazwa pochodzi jednak od Johna Wilsona, angielskiego matematyka i późniejszego sędziego, który sformułował je około 1770 roku - bez dowodu.

Opublikował je Edward Waring, dodając, że dowód będzie trudny, bo brakuje dobrej notacji dla liczb pierwszych. Skomentował to Carl Friedrich Gauss, któremu przypisuje się uwagę, że potrzeba tu „nie notacji, lecz metod” - i podanie dowodu od ręki. Pierwszy opublikowany dowód pochodzi od Josepha Lagrange’a (1771).

Najczęstsze pytania

Czy twierdzenie działa w obie strony? Tak - i to je wyróżnia. Reszta $-1$ z dzielenia $(n-1)!$ przez $n$ zachodzi dokładnie dla liczb pierwszych.

Dlaczego $n = 4$ jest wyjątkiem? Bo $4 = 2 \cdot 2$ , a w iloczynie $3! = 1 \cdot 2 \cdot 3$ dwójka występuje tylko raz - brakuje drugiego czynnika, który dopełniłby $4$ . Dla większych kwadratów liczb pierwszych problem znika, bo $2p$ mieści się poniżej $p^2$ .

Czym różni się od małego twierdzenia Fermata? Twierdzenie Fermata daje warunek konieczny pierwszości (i dają się je oszukać liczbom Carmichaela), a twierdzenie Wilsona - warunek równoważny. Za to Fermata liczy się szybko, a Wilsona bardzo wolno.

Czy istnieje szybszy sposób policzenia $(p-1)! \bmod p$ ? Nie jest znany żaden istotnie szybszy niż wymnożenie po kolei. Gdyby powstał, twierdzenie Wilsona stałoby się praktycznym testem pierwszości.

Co to są liczby pierwsze Wilsona? Liczby pierwsze $p$ , dla których $p^2$ dzieli $(p-1)! + 1$ (czyli warunek zachodzi „mocniej”). Znamy tylko trzy: $5$ , $13$ oraz $563$ - i nie wiadomo, czy jest ich nieskończenie wiele.

Podsumowanie

$p > 1$ jest pierwsza wtedy i tylko wtedy, gdy $(p-1)! \equiv -1 \pmod p$ .
Dowód polega na parowaniu liczb z ich odwrotnościami modulo $p$ ; samotne zostają tylko $1$ i $p-1$ .
Twierdzenie odwrotne również jest prawdziwe: dla złożonych $n > 4$ zachodzi $(n-1)! \equiv 0$ ; jedyny wyjątek to $n = 4$ .
Jako test pierwszości jest bezużyteczne - wymaga około $n$ mnożeń.
Znane od około 1000 roku (Ibn al-Hajsam), nazwane po Wilsonie, udowodnione przez Lagrange’a w 1771 roku.