Pojdi na vsebino

Wilsonov izrek

Iz Wikipedije, proste enciklopedije

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 v izreku:

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

[uredi | uredi kodo]

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

[uredi | uredi kodo]

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


(OEIS A000142)


(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

[uredi | uredi kodo]

Praštevilski testi

[uredi | uredi kodo]

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

[uredi | uredi kodo]

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

da se dobi kongruenco:

To postane:

ali:

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!)2 kongruentno (−1).

Formule praštevil

[uredi | uredi kodo]

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

p-iška funkcija gama

[uredi | uredi kodo]

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

Gaussova posplošitev

[uredi | uredi kodo]

Gauss je dokazal, da velja:[6]

kjer predstavlja p liho praštevilo in 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

[uredi | uredi kodo]

Sklici

[uredi | uredi kodo]
  1. The Universal Book of Mathematics. David Darling, p. 350.
  2. O'Connor, John Joseph; Robertson, Edmund Frederick, »Abu Ali al-Hasan ibn al-Haytham«, Arhiv zgodovine matematike MacTutor (v angleščini), Univerza v St Andrewsu
  3. Edward Waring, Meditationes Algebraicae (Cambridge, England: 1770), page 218 (in Latin). In the third (1782) edition of Waring's Meditationes Algebraicae, Wilson's theorem appears as problem 5 on page 380. On that page, Waring states: "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger." (A man most illustrious and most skilled in mathematics, Squire John Wilson, found this most elegant property of prime numbers.)
  4. Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers" (Proof of a new theorem concerning prime numbers), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Berlin), vol. 2, pages 125–137 (1771).
  5. Giovanni Vacca (1899) "Sui manoscritti inediti di Leibniz" (On unpublished manuscripts of Leibniz), Bollettino di bibliografia e storia delle scienze matematiche ... (Bulletin of the bibliography and history of mathematics), vol. 2, pages 113–116; see page 114 (in Italian). Vacca quotes from Leibniz's mathematical manuscripts kept at the Royal Public Library in Hanover (Germany), vol. 3 B, bundle 11, page 10:
  6. Gauss, DA, art. 78

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.

Zunanje povezave

[uredi | uredi kodo]