Twierdzenie Wilsona - Wilson's theorem

W teorii liczb , Twierdzenie Wilsona stwierdza, że liczba naturalna n > 1 jest liczbą pierwszą , wtedy i tylko wtedy, gdy iloczyn wszystkich liczb całkowitych dodatnich mniej niż n jest mniejsza niż wielokrotność n . Czyli (używając notacji arytmetyki modularnej ), silnia spełnia ${\ Displaystyle (n-1)! = 1 \ razy 2 \ razy 3 \ razy \ cdots \ razy (n-1)}$

${\displaystyle (n-1)!\\equiv \;-1{\pmod {n}}}$

dokładnie wtedy, gdy n jest liczbą pierwszą. Innymi słowy, dowolna liczba n jest liczbą pierwszą wtedy i tylko wtedy, gdy ( n  − 1)! + 1 jest podzielne przez n .

Historia

Twierdzenie to zostało sformułowane przez Ibn al-Haythama (ok. 1000 AD), aw XVIII wieku przez Johna Wilsona . Edward Waring ogłosił to twierdzenie w 1770 roku, chociaż ani on, ani jego uczeń Wilson nie mogli tego udowodnić. Lagrange przedstawił pierwszy dowód w 1771 roku. Istnieją dowody na to, że Leibniz był świadom tego wyniku sto lat wcześniej, ale nigdy go nie opublikował.

Przykład

Dla każdej z wartości n od 2 do 30, poniższa tabela pokazuje liczbę ( n  − 1)! a resztę gdy ( n  − 1)! dzieli się przez n . (W zapisie arytmetyki modularnej resztę z dzielenia m przez n zapisuje się m mod n .) Kolor tła jest niebieski dla wartości pierwszych n , złoty dla wartości złożonych .

Tabela silni i jej reszty modulo n

${\ Displaystyle n}$	${\displaystyle (n-1)!}$ (sekwencja A000142 w OEIS )	${\displaystyle (n-1)!\ {\bmod {\}}n}$ (sekwencja A061006 w OEIS )
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

Dowody

Poniższe dowody (dla modułów pierwszych) wykorzystują fakt, że klasy pozostałości modulo a liczba pierwsza są polami - zobacz artykuł pole pierwsze po więcej szczegółów. Twierdzenie Lagrange'a , w którym stwierdza się, że w każdym polu należy wielomian od stopnia n ma co najwyżej n korzeni , jest potrzebna dla wszystkich dowodów.

Moduł kompozytowy

Jeśli n jest złożone, jest podzielne przez pewną liczbę pierwszą q , gdzie 2 ≤ q ≤ n − 2 . Ponieważ dzieli , niech na jakąś liczbę całkowitą . Załóżmy, ze względu na sprzeczność, że ( n − 1)! były zgodne z -1 (mod n ), gdzie n jest złożone. Wtedy (n-1)! byłaby również przystająca do -1 (mod q ), co implikuje, że dla pewnej liczby całkowitej, która pokazuje (n-1)! przystające do -1 (mod q). Ale ( n  − 1)! ≡ 0 (mod  q ) przez fakt, że q jest wyrazem w (n-1)! robienie (n-1)! wielokrotność q. Sprzeczność została osiągnięta. ${\displaystyle q}$${\ Displaystyle n}$${\displaystyle n=qk}$${\displaystyle k}$${\ Displaystyle (n-1)! \ równoważ -1 \ ({\ tekst {mod}} \ n)}$${\ Displaystyle (n-1)! = nm-1 = (qk) m-1 = q (km)-1}$${\ Displaystyle m}$

W rzeczywistości więcej jest prawdą. Z jedynym wyjątkiem 4, gdzie 3! = 6 ≡ 2 (mod 4), jeśli n jest złożone, to ( n  − 1)! jest przystający do 0 (mod  n ). Dowód jest podzielony na dwa przypadki: Po pierwsze, w przypadku n może być brane jako iloczyn dwóch nierównych ilościach, n = AB , gdzie 2 ≤  < b  ≤  n  - 2, wówczas oba i b pojawia się w produkcie 1X 2 × ... × ( n − 1) = ( n − 1)! oraz ( n  − 1)! będzie podzielna przez n . Jeśli n nie ma takiego rozkładu na czynniki, to musi to być kwadrat jakiejś liczby pierwszej q , q  > 2. Ale wtedy 2 q  <  q ²  =  n , zarówno q , jak i 2 q będą czynnikami ( n  − 1)!, i znowu n dzieli ( n  − 1)!.

Moduł pierwotny

Podstawowy dowód

Wynik jest trywialny, gdy p = 2 , więc załóżmy, że p jest nieparzystą liczbą pierwszą, p ≥ 3 . Ponieważ klasy reszt (mod p ) są polami, każda niezerowa a ma unikalną odwrotność multiplikatywną, a ^-1 . Twierdzenie Lagrange'a oznacza, że tylko wartości dla których ≡ ^-1 (mod p ) są ≡ ± 1 (mod p ) (ze względu na zbieżność ² ≡ 1 może mieć co najwyżej dwa pierwiastki (mod p )). Zatem z wyjątkiem ±1, współczynniki ( p − 1)! mogą być ułożone w nierówne pary, gdzie iloczyn każdej pary to ≡ 1 (mod p ) . To dowodzi twierdzenia Wilsona.

Na przykład, jeśli p = 11 ,

${\ Displaystyle 10! = [(1 \ cdot 10)] \ cdot [(2 \ cdot 6) (3 \ cdot 4) (5 \ cdot 9) (7 \ cdot 8)] \ równoważne [-1] \ cdot [1\cdot 1\cdot 1\cdot 1]\equiv -1{\pmod {11}}.}$

Dowód przy użyciu małego twierdzenia Fermata

Ponownie, wynik jest trywialny dla p  = 2, więc załóżmy, że p jest nieparzystą liczbą pierwszą, p ≥ 3 . Rozważ wielomian

${\ Displaystyle g (x) = (x-1) (x-2) \ cdots (x-(p-1)).}$

g ma stopień p − 1 , wyraz wiodący x ^{p − 1} i wyraz stały ( p − 1)! . Jego p − 1 pierwiastkami to 1, 2, ..., p − 1 .

Teraz rozważ

${\ Displaystyle h (x) = x ^ {p-1} -1.}$

h ma również stopień p − 1 i wyraz wiodący x ^{p − 1} . Modulo p , małe twierdzenie Fermata mówi, że ma również te same pierwiastki p − 1 , 1, 2, ..., p − 1 .

Na koniec rozważ

${\ Displaystyle f (x) = g (x)-h (x).}$

f ma co najwyżej stopień p  − 2 (ponieważ wyrazy wiodące się anulują), a modulo p ma również p − 1 pierwiastki 1, 2, ..., p − 1 . Ale twierdzenie Lagrange'a mówi, że nie może mieć więcej niż p  − 2 pierwiastków. Dlatego f musi być identycznie zerowe (mod p ), więc jego człon stały to ( p − 1)! + 1 ≡ 0 (mod p ) . To jest twierdzenie Wilsona.

Dowód przy użyciu twierdzeń Sylowa

Twierdzenie Wilsona można wydedukować z konkretnego zastosowania twierdzeń Sylowa . Niech p będzie liczbą pierwszą. Natychmiast wywnioskować, że grupa symetryczna ma dokładnie elementy porządku p , a mianowicie p- cykle . Z drugiej strony, każdy Sylow p -subgroup w to kopia . Stąd wynika, że ​​liczba p- podgrup Sylowa wynosi . Trzecie twierdzenie Sylowa implikuje: ${\displaystyle S_{p}}$${\displaystyle (p-1)!}$${\displaystyle C_{p}}$${\displaystyle S_{p}}$${\displaystyle C_{p}}$${\ Displaystyle n_ {p} = (p-2)!}$

${\displaystyle (p-2)!\equiv 1{\pmod {p}}.}$

Mnożenie obu stron przez ( p − 1) daje

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

czyli wynik.

Dowód za pomocą prymitywnych korzeni

Niech a będzie pierwiastkiem pierwotnym modulo n z p . Następnie , i wszystkie inne mają jako odwrotność multiplikatywną, ponieważ . Jak przebiega przez wszystkie liczby całkowite od pierwszych do p , skończyliśmy. ${\ Displaystyle a ^ {\ Frac {p-1} {2}} \ równoważnik -1 {\ pmod {p}}}$${\ Displaystyle a ^ {k}}$${\ Displaystyle a ^ {pk-1}}$${\ Displaystyle a ^ {k} a ^ {pk-1} = a ^ {p-1} \ równoważnik 1 {\ pmod {p}}}$${\ Displaystyle a ^ {k}}$

Aplikacje

Testy pierwszości

W praktyce twierdzenie Wilsona jest bezużyteczne jako test pierwszości, ponieważ obliczanie ( n − 1)! modulo n dla dużego n jest obliczeniowo złożone i znane są znacznie szybsze testy pierwszości (w rzeczywistości nawet podział prób jest znacznie bardziej wydajny).

Reszty kwadratowe

Używając twierdzenia Wilsona, dla dowolnej nieparzystej liczby pierwszej p = 2 m + 1 , możemy przestawić lewą stronę

${\ Displaystyle 1 \ cdot 2 \ cdots (p-1) \ \ równoważnik \ -1 \ {\ pmod {p}}}$

uzyskać równość

${\ Displaystyle 1 \ cdot (p-1) \ cdot 2 \ cdot (p-2) \ cdots m \ cdot (pm) \ \ równoważny \ 1 \ cdot (-1) \ cdot 2 \ cdot (-2) \ cdots m\cdot (-m)\ \equiv \ -1{\pmod {p}}.}$

To staje się

${\ Displaystyle \ prod _ {j = 1} ^ {m} \ j ^ {2} \ \ equiv (-1) ^ {m + 1} {\ pmod {p}}}$

lub

${\ Displaystyle (m!) ^ {2} \ ekwiwalent (-1) ^ {m + 1} {\ pmod {p}}.}$

Możemy wykorzystać ten fakt do udowodnienia części słynnego wyniku: dla dowolnej liczby pierwszej p takiej, że p  ≡ 1 (mod 4) , liczba (−1) jest kwadratem ( reszta kwadratowa ) mod p . Załóżmy, że p  = 4 k  + 1 dla pewnej liczby całkowitej k . Następnie możemy wziąć m  = 2 k powyżej i wyciągnąć wniosek, że ( m !) ² jest przystające do (−1).

Wzory na liczby pierwsze

Twierdzenie Wilsona zostało użyte do skonstruowania wzorów na liczby pierwsze , ale są one zbyt wolne, aby mieć praktyczną wartość.

p-adyczna funkcja gamma

Twierdzenie Wilsona pozwala na zdefiniowanie p-adycznej funkcji gamma .

uogólnienie Gaussa

Gauss to udowodnił

${\ Displaystyle \ prod _ {k = 1 \ atop \ gcd (k, m) = 1} ^ {m} \! \! k \ \ equiv {\ zacząć {przypadki} -1 {\ pmod {m}} i {\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{w przeciwnym razie }}\end{przypadki}}}$

gdzie p reprezentuje nieparzystą liczbę pierwszą i dodatnią liczbę całkowitą. Wartości m, dla których iloczyn wynosi -1 są dokładnie tymi, dla których istnieje pierwiastek pierwotny modulo m . ${\ Displaystyle \ alfa}$

To dodatkowo uogólnia na fakt, że w każdym skończonej grupy Abelowych albo produkt wszystkich elementów jest tożsamość czy istnieje dokładnie jeden element z rzędu 2 (ale nie obydwa). W tym ostatnim przypadku produkt wszystkich elementów równa  .

Zobacz też

• Wilson pierwszy
• Tabela kongruencji

Uwagi

Bibliografia

Linki zewnętrzne

• "Twierdzenie Wilsona" , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Weisstein, Eric W. „Twierdzenie Wilsona” . MatematykaŚwiat .
• Dowód systemu Mizar : http://mizar.org/version/current/html/nat_5.html#T22