Twierdzenie Wilsona

Sir John Wilson (1741-1793) zauważył, że gdy $p$ jest liczbą pierwszą, wtedy reszta z dzielenia liczby $(p-1)!$ przez $p$ jest zawsze równa $p-1$.

Dla każdej liczby pierwszej $p$ liczba $(p-1)!+1$ jest podzielna przez $p$.

Dowód. Niech $p$ będzie liczbą pierwszą i niech $f(x)=(x-1)(x-2)\ldots(x-p+1) - x^{p-1} + 1$ będzie wielomianem stopnia $p-2$ o całkowitych współczynnikach. Dla $x = 1, 2, \ldots, p - 1$ mamy, w myśl twierdzenia Fermata, $p|x^p-x = x(x^{p-1} - 1)$, skąd $p|x^{p-1} - 1$.
Dla $x = 1, 2, \ldots, p - 1$ otrzymujemy $p|(x-1)(x-2)\ldots(x-p+1)$, ponieważ dla takich $x$ jeden z czynników tego iloczynu jest równy $0$. Stąd wnioskujemy, że $p|f(x)$. Na podstawie wniosku z twierdzenia Lagrange'a, wszystkie współczynniki wielomianu oraz wyraz wolny, są podzielne przez $p$.

Kryterium Wilsona dla liczb pierwszych
Jeżeli dla liczby naturalnej $n \gt 1$ liczba $(n-1)! + 1$ jest podzielna przez $n$, to $n$ musi być liczbą pierwszą. Gdyby $n$ było liczbą złożoną, to $n = ab$, gdzie $1 \lt a$, $b \lt n$ i liczba $a$ byłaby jednym z czynników iloczynu $1 \cdot 2 \cdot \ldots \cdot (n-1)$, a więc liczba $(n-1)! + 1$ przy dzieleniu przez $a$ dawałaby resztę $1$. Zachodzi sprzeczność, ponieważ będąc podzielną przez $n$, musi być podzielna przez $a$, dowodzi to, że liczba $n$ musi być pierwszą.

Na to, aby liczba naturalna większa od $1$ była liczbą pierwszą, potrzeba i wystarcza, aby liczba $(n-1)!+1$ była podzielna przez $n$. W odróżnieniu od kryterium Fermata warunek Wilsona jest jednocześnie konieczny i wystarczający. Teoretycznie, za pomocą jednego tylko dzielenia możemy się przekonać, czy liczba jest, czy też nie jest pierwszą. Praktycznie warunek znaczenia wielkiego nie ma, ponieważ nie jest znany algorytm do szybkiego obliczania liczby $n!$.