White Shore: Dowód twierdzenia Wilsona

Dowód twierdzenia Wilsona

(1)

$(n-1)!\equiv -1 \ (mod\ n) \Leftrightarrow n\ \hbox{jest pierwsza, dla }n>1$

Iplikacja w lewo jest trywialna. Jeżeli $n>1$ nie jest liczbą pierwszą, to istnieje jej czynnik pierwszy $p$ , który musi dzielić $(n-1)!$ jako, że jest mniejszy od $n$ . $(n-1)!$ nie może więc przystawać do $-1$ modulo $n$ (Gdyby $(n-1)!$ przystawałoby do $-1$ modulo $n$ , przystawałoby także do $-1$ modulo $p$ a nie przystaje).

Implikacja w prawo jest trudniejsza. Zakładamy, że $(n-1)!\equiv -1 \ (mod\ n)$ . Można to wykazać, grupując w pary liczby wraz z ich antymodułami względem $p$ . Jeżeli $n\perp p$ , to wiemy, że istnieje liczba $n'$ taka, że $n'n\equiv 1 \ (mod\ p)$ . Liczba $n'$ jest tu odwrotnością $n$ , także liczba $n$ jest odwrotnością $n'$ . Każde dwie odwrotności liczby $n$ przystają do siebie, ponieważ $nn'\equiv nn''\Rightarrow n'\equiv n''$ .

Każdą liczbę pomiędzy $1$ a $p-1$ stawiamy w parze z jej odwrotnością. Ponieważ iloczyn każdej liczby z jej odwrotnością przystaje do $1$ modulo $p$ , więc iloczyn wszystkich liczb z tak utworzonych par również przystaje do 1. Na tej samej zasadzie $(p-1)!\equiv 1$ .

Zauważmy, że dla $p=5$ mamy następującą sytuację: $1'=1$ , $2'=3$ , $3'=2$ , $4'=4$ . Musimy, więc określić, które liczby $x$ są swoimi odwrotnościami. Dla takich liczb zachodzi $x^{2}\equiv 1 \ (mod\ p)$ . Wiemy, że taka kongruencja ma dwa rozwiązania, gdy $p>2$ (jeżeli $p=2$ , to $(p-1)!\equiv -1$ ). Rozwiązaniami są $1$ i $p-1$ , a pozostałe liczby (między $1$ a $p-1$ ) stoją w parach. Ostatecznie więc $(p-1)!$\equiv 1\cdot (p-1)\equiv -1$ .

Literatura

1. R. L. Graham, D. E. Knuth, O. Patashnik - Matematyka Konkretna

wersja strony: 3, ostatnia edycja: 1214758143|%e %b %Y, %H:%M %Z (%O temu)

edytuj tagi historia pliki drukuj narzędzia + opcje