Twierdzenie Wilsona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

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[edytuj]

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 . Rozpatrzmy w nim równanie:

Ma ono te same rozwiązania co równanie , czyli

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 , dla p różnego od 2, zachodzi nierówność -1 ≠ 1). Wynika stąd, że jedynymi elementami ciała , 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 ·y = 1, gdzie xy. 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:

.

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:

,

czyli jest podzielna przez .

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·b = p. Wtedy . Zatem

i stąd (pamiętając, że )

,

więc

.

Tak więc

i liczba nie jest podzielna przez .

Uogólnienie[edytuj]

Istnieje uogólnienie twierdzenia Wilsona, autorstwa Gaussa:

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

Dla m = 2 zachodzi

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