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 ${\displaystyle (n-1)!=1\cdot 2\cdot 3\cdot \cdots \cdot (n-1)}$ v izreku:

${\displaystyle (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.^[1]

Zgodovina

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

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

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

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

da se dobi kongruenco:

${\displaystyle 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:

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

ali:

${\displaystyle (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:^[6]

${\displaystyle \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 ${\displaystyle \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