Wilsonov izrek

Wilsonov izrek v teoriji števil pravi, da je naravno število n > 1 praštevilo, če in samo če je zmnožek vseh naravnih števil, ki so manjša od n za ena manj od mnogokratnika od n. To pomeni, da (z uporabo zapisa modularne aritmetike) fakulteta $(n-1)!=1\cdot 2\cdot 3\cdot \cdots \cdot (n-1)$ v izreku:

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

velja, ko je n praštevilo. Z drugimi besedami, vsako število n je praštevilo, če in samo če je (n − 1)! + 1 deljivo z n.

Zgodovina

Izrek je odkril Ibn Al Haitam (ok. 1000 n. št.) in John Wilson v 18. stoletju. Edward Waring je izrek oznanil leta 1770, toda nihče ga ni znal dokazati. Prvi dokaz je podal Lagrange leta 1771. Obstajajo dokazi, da je dokaz že eno stoletje prej vedel Leibniz, toda ga ni nikoli objavil.

Primer

Za vsako izmed vrednosti n od 2 do 30, podaja sledeča tabela število (n − 1)! in ostanek pri deljenju (n − 1)! z n. (V modularni aritmetiki se ostanek števila m pri deljenju z n zapiše m mod n.) Barva ozadja je modra za praštevila od n in zlata za sestavljena števila.

Seznam fakultet in njihovih ostankov modula n

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

Uporaba

Praštevilski testi

V praksi je Wilsonov izrek neuporaben kot praštevilski test, saj je izračun (n − 1)! modula n za velik n izračunljivo zelo kompleksen, obstajajo pa tudi veliko hitrejši praštevilski testi (še poskusno deljenje je veliko hitreje).

Kvadratni ostanki

Z uporabo Wilsonovega izreka za katerokoli praštevilo p = 2m + 1 se lahko preoblikuje levo stran kongruence:

$1\cdot 2\cdots (p-1)\ \equiv \ -1\ {\pmod {p}}\!\,,$

da se dobi kongruenco:

$1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv \ -1{\pmod {p}}\!\,.$

To postane:

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

ali:

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

To dejstvo se lahko uporabi za dokaz dela slavnega rezultata: za katerokoli praštevilo p, za katerega velja p ≡ 1 (mod 4), je število (−1) kvadrat (kvadratni ostanek) mod p. Predpostavi se, da je p = 4k + 1 za neko celo število k. Potem se lahko vzame m = 2k zgoraj in sklepa, da je (m!)² kongruentno (−1).

Formule praštevil

Wilsonov izrek se uporablja tudi za konstrukcijo formul za praštevila, toda je prepočasen za praktično uporabo.

p-iška funkcija gama

Wilsonov izrek se uporablja za definiranje p-iške funkcije gama.

Gaussova posplošitev

Gauss je dokazal, da velja:

$\prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{če }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{sicer}}\end{cases}}$

kjer predstavlja p liho praštevilo in $\alpha$ naravno število. Vrednosti od m za produkt −1 so tiste, kjer je primitivni koren modula m.

To se še naprej posploši v dejstvo, da je v katerikoli končni Abelovi grupi ali produkt vseh elementov identiteta ali je natanko eden element a reda 2 (a ne oboje). V zadnjem primeru, je produkt vseh elementov enak a

Glej tudi

• Wilsonovo praštevilo
• tabela kongruenc

Viri

Disquisitiones Arithmeticae je bila prevedena iz Gaussove ciceronske latinščine v angleščino in nemščino. Nemška verzija vsebuje vse njegove zapise o teoriji števil: vse dokaze kvadratne recipročnosti, določitev znaka Gaussovih vsot, raziskovanja bikvadratne recipročnosti in neobjavljene opombe.

• Gauss, Carl Friedrich; Clarke, Arthur A. (1986), Disquisitiones Arithemeticae (2. corrected izd.), New York: Springer, ISBN 0-387-96254-9 (translated into English){{citation}}: Vzdrževanje CS1: postscript (povezava).
• Gauss, Carl Friedrich; Maser, H. (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (2. izd.), New York: Chelsea, ISBN 0-8284-0191-8 (translated into German){{citation}}: Vzdrževanje CS1: postscript (povezava).
• Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea.
• Ore, Oystein (1988). Number Theory and its History. Dover. str. 259–271. ISBN 0-486-65620-9.

Zunanje povezave

• »Wilson theorem«, Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric Wolfgang. »Wilson's Theorem«. MathWorld.
• Dokaz v sistemu Mizar: http://mizar.org/version/current/html/nat_5.html#T22