Wilsonsova věta - Wilsons theorem - Wikipedia

v teorie čísel, Wilsonova věta uvádí, že a přirozené číslo n > 1 je a prvočíslo kdyby a jen kdyby produkt všech kladná celá čísla méně než n je jeden méně než násobek n. To je (pomocí zápisů z modulární aritmetika ), faktoriál ${ Displaystyle (n-1)! = 1 krát 2 krát 3 krát cdots krát (n-1)}$ splňuje

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

přesně kdy n je prvočíslo. Jinými slovy, libovolné číslo n je prvočíslo tehdy a jen tehdy, (n - 1)! + 1 je dělitelné n.^[1]

Dějiny

Tuto větu uvedl Ibn al-Haytham (c. 1000 nl),^[2] a v 18. století John Wilson.^[3] Edward Waring oznámil teorém v roce 1770, ačkoli to nedokázal ani on, ani jeho student Wilson. Lagrange dal první důkaz v roce 1771.^[4] Existují důkazy o tom Leibniz byl si také vědom výsledku před sto lety, ale nikdy ho nezveřejnil.^[5]

Příklad

Pro každou z hodnot n od 2 do 30, následující tabulka ukazuje počet (n - 1)! a zbytek, když (n - 1)! je rozděleno n. (V zápisu z modulární aritmetika, zbytek, když m je rozděleno n je psáno m mod n.) Barva pozadí je pro primární hodnoty n, zlato za kompozitní hodnoty.

Tabulka faktoriálu a jeho zbytek modulo n

${ displaystyle n}$	${ displaystyle (n-1)!}$ (sekvence A000142 v OEIS )	${ displaystyle (n-1)! { bmod {}} n}$ (sekvence A061006 v 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

Důkazy

Oba důkazy (pro prvočíselné moduly) níže využívají skutečnost, že třídy reziduí modulující prvočíslo jsou a pole —Viz článek hlavní pole Více podrobností.^[6] Lagrangeova věta, který uvádí, že v jakékoli oblasti a polynomiální z stupeň n má nanejvýš n kořeny, je potřeba pro oba důkazy.

Složený modul

Li n je složený, je dělitelný nějakým prvočíslem q, kde 2 ≤ q ≤ n − 2. Li (n − 1)! byly shodné s -1 (mod n) pak by také bylo shodné s −1 (mod q). Ale (n - 1)! ≡ 0 (modq).

Ve skutečnosti platí více. S jedinou výjimkou 4, kde 3! = 6 ≡ 2 (mod 4), pokud n je složený pak (n - 1)! je shodný s 0 (modn). Důkaz je rozdělen do dvou případů: Nejprve, pokud n lze započítat jako součin dvou nerovných čísel, n = ab, kde 2 ≤A < b ≤ n - 2, pak oba A a b se objeví v produktu 1 × 2 × ... × (n − 1) = (n − 1)! a (n - 1)! bude dělitelný n. Li n nemá takovou faktorizaci, pak to musí být čtverec nějakého prvočísla q, q > 2. Ale potom 2q < q² = n, oba q a 2q budou faktory (n - 1)! A znovu n rozděluje (n − 1)!.

Prime modul

Základní důkaz

Výsledek je triviální, když p = 2, tak předpokládejme p je zvláštní prime, p ≥ 3. Protože třídy reziduí (mod p) jsou pole, každé nenulové A má jedinečnou multiplikativní inverzi, A⁻¹. Lagrangeova věta znamená, že jediné hodnoty A pro který A ≡ A⁻¹ (mod p) jsou A ≡ ± 1 (mod p) (protože shoda A² ≡ 1 může mít maximálně dva kořeny (mod p)). Proto, s výjimkou ± 1, faktory (p − 1)! lze uspořádat do nerovných párů,^[7] kde je produkt každého páru ≡ 1 (mod p). To dokazuje Wilsonovu větu.

Například pokud p = 11,

${ displaystyle 10! = [(1 cdot 10)] cdot [(2 cdot 6) (3 cdot 4) (5 cdot 9) (7 cdot 8)] equiv [-1] cdot [1 cdot 1 cdot 1 cdot 1] equiv -1 { pmod {11}}.}$

Důkaz pomocí Fermatovy malé věty

Výsledek je opět triviální p = 2, tak předpokládejme p je zvláštní prime, p ≥ 3. Zvažte polynom

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

G má titul p − 1, vedoucí termín X^{p − 1}a konstantní termín (p − 1)!. Své p − 1 kořeny jsou 1, 2, ..., p − 1.

Nyní zvažte

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

h má také titul p − 1 a vedoucí termín X^{p − 1}. Modulo p, Fermatova malá věta říká, že má také to samé p − 1 kořeny, 1, 2, ..., p − 1.

Nakonec zvažte

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

F má titul nanejvýš p - 2 (protože hlavní termíny se ruší) a modulo p má také p − 1 kořeny 1, 2, ..., p − 1. Lagrangeova věta však říká, že nemůže mít více než p - 2 kořeny. Proto, F musí být shodně nula (mod p), takže jeho konstantní člen je (p - 1)! + 1 ≡ 0 (mod p). Toto je Wilsonova věta.

Důkaz použití Sylowových vět

Je možné odvodit Wilsonovu větu z konkrétní aplikace Sylowovy věty. Nechat p být předseda. Okamžitě lze odvodit, že symetrická skupina ${ displaystyle S_ {p}}$ má přesně ${ displaystyle (p-1)!}$ prvky objednávky p, jmenovitě p-cykly ${ displaystyle C_ {p}}$. Na druhou stranu každý Sylow p-podskupina v ${ displaystyle S_ {p}}$ je kopií ${ displaystyle C_ {p}}$. Z toho tedy vyplývá, že počet Sylow p-skupiny jsou ${ displaystyle n_ {p} = (p-2)!}$. Třetí Sylowova věta naznačuje

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

Vynásobením obou stran (p − 1) dává

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

to je výsledek.

Aplikace

Testy originality

V praxi je Wilsonova věta zbytečná jako test primality protože práce na počítači (n - 1)! modulo n pro velké n je výpočetně složité a jsou známy mnohem rychlejší testy primality (ve skutečnosti dokonce zkušební rozdělení je podstatně efektivnější).

Kvadratické zbytky

Pomocí Wilsonovy věty pro jakékoli liché prvočíslo p = 2m + 1, můžeme přeskupit levou stranu

${ displaystyle 1 cdot 2 cdots (p-1) equiv -1 { pmod {p}}}$

dosáhnout rovnosti

${ Displaystyle 1 cdot (p-1) cdot 2 cdot (p-2) cdots m cdot (pm) equiv 1 cdot (-1) cdot 2 cdot (-2) cdots m cdot (-m) equiv -1 { pmod {p}}.}$

To se stává

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

nebo

${ displaystyle (m!) ^ {2} equiv (-1) ^ {m + 1} { pmod {p}}.}$

Tuto skutečnost můžeme použít k prokázání části slavného výsledku: pro jakýkoli prime p takhle p ≡ 1 (mod 4), číslo (−1) je čtverec (kvadratický zbytek ) mod p. Předpokládejme p = 4k + 1 pro celé číslo k. Pak můžeme vzít m = 2k výše, a docházíme k závěru, že (m!)² je shodný s (-1).

Vzorce pro prvočísla

Wilsonova věta byla použita ke konstrukci vzorce pro prvočísla, ale jsou příliš pomalé na to, aby měly praktickou hodnotu.

funkce gama p-adic

Wilsonova věta umožňuje definovat funkce gama p-adic.

Gaussovo zobecnění

Gauss dokázal to^[8]

${ displaystyle prod _ {k = 1 na vrcholu gcd (k, m) = 1} ^ {m} ! ! k equiv { begin {cases} -1 { pmod {m}} & { text {if}} m = 4, ; p ^ { alpha}, ; 2p ^ { alpha} ; ; , 1 { pmod {m}} & { text {jinak }} end {cases}}}$

kde p představuje liché prvočíslo a ${ displaystyle alpha}$ kladné celé číslo. Hodnoty m pro které je produkt −1, jsou přesně ty, kde existuje a primitivní root modulo m.

To dále zobecňuje skutečnost, že v každém konečný abelianská skupina, buď produkt všech prvků je identita, nebo existuje přesně jeden prvek A z objednat 2 (ale ne obojí). V druhém případě je součin všech prvků stejnýA.

Viz také

• Wilson připravit
• Tabulka shody

Poznámky

Reference

externí odkazy

• „Wilsonova věta“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Weisstein, Eric W. „Wilsonova věta“. MathWorld.
• Systém Mizar důkaz: http://mizar.org/version/current/html/nat_5.html#T22