Ogled vira Wilsonov izrek

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

: <math> (n-1)!\ \equiv\; -1 \pmod n \!\, </math>

velja, ko je ''n'' praštevilo. Z drugimi besedami, vsako število ''n'' je praštevilo, če in samo če je (''n''&#x2009;−&#x2009;1)!&nbsp;+&nbsp;1 deljivo z ''n''.<ref>''The Universal Book of Mathematics.'' David Darling, p. 350.</ref>

== Zgodovina ==

Izrek je odkril [[Alhacen|Ibn Al Haitam]] (ok. 1000 n. št.)<ref>{{MacTutor Biography|id=Al-Haytham|title=Abu Ali al-Hasan ibn al-Haytham}}</ref> in [[John Wilson (matematik)|John Wilson]] v 18. stoletju.<ref>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 [https://books.google.com/books?id=1MNbAAAAQAAJ&pg=PA380#v=onepage&f=false 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.)</ref> [[Edward Waring]] je izrek oznanil leta 1770, toda nihče ga ni znal dokazati. Prvi dokaz je podal [[Joseph-Louis de Lagrange|Lagrange]] leta 1771.<ref>Joseph Louis Lagrange, [https://books.google.com/books?id=_-U_AAAAYAAJ&pg=PA125#v=onepage&q&f=false "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).</ref> Obstajajo dokazi, da je dokaz že eno stoletje prej vedel [[Gottfried Wilhelm Leibniz|Leibniz]], toda ga ni nikoli objavil.<ref>[[Giovanni Vacca (mathematician)|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 [https://books.google.com/books?id=vqwSAQAAMAAJ&pg=PA114#v=onepage&q&f=false 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:</ref>

== Primer ==

Za vsako izmed vrednosti ''n'' od 2 do 30, podaja sledeča tabela število (''n''&#x2009;−&#x2009;1)! in ostanek pri deljenju (''n''&#x2009;−&#x2009;1)! z ''n''. (V [[modularna aritmetika|modularni aritmetiki]] se ostanek števila ''m'' pri deljenju z ''n'' zapiše ''m'' mod ''n''.) Barva ozadja je modra za <span style="background-color:#94DCF2">praštevila</span> od ''n'' in zlata za <span style="background-color:#E6C647">sestavljena</span> števila.
{| class="wikitable" style="text-align:right"
|+Seznam fakultet in njihovih ostankov modula ''n''
!<math>n</math>
!<math>(n-1)!</math> <br /><br /> {{OEIS|id=A000142}}
!<math>(n-1)!\ \bmod\ n</math> <br /><br /> {{OEIS|id=A061006}}
|- style="background-color:#94DCF2"
|2
|1
|1
|- style="background-color:#94DCF2"
|3
|2
|2
|- style="background-color:#E6C647"
|4
|6
|2
|- style="background-color:#94DCF2"
|5
|24
|4
|- style="background-color:#E6C647"
|6
|120
|0
|- style="background-color:#94DCF2"
|7
|720
|6
|- style="background-color:#E6C647"
|8
|5040
|0
|- style="background-color:#E6C647"
|9
|40320
|0
|- style="background-color:#E6C647"
|10
|362880
|0
|- style="background-color:#94DCF2"
|11
|3628800
|10
|- style="background-color:#E6C647"
|12
|39916800
|0
|- style="background-color:#94DCF2"
|13
|479001600
|12
|- style="background-color:#E6C647"
|14
|6227020800
|0
|- style="background-color:#E6C647"
|15
|87178291200
|0
|- style="background-color:#E6C647"
|16
|1307674368000
|0
|- style="background-color:#94DCF2"
|17
|20922789888000
|16
|- style="background-color:#E6C647"
|18
|355687428096000
|0
|- style="background-color:#94DCF2"
|19
|6402373705728000
|18
|- style="background-color:#E6C647"
|20
|121645100408832000
|0
|- style="background-color:#E6C647"
|21
|2432902008176640000
|0
|- style="background-color:#E6C647"
|22
|51090942171709440000
|0
|- style="background-color:#94DCF2"
|23
|1124000727777607680000
|22
|- style="background-color:#E6C647"
|24
|25852016738884976640000
|0
|- style="background-color:#E6C647"
|25
|620448401733239439360000
|0
|- style="background-color:#E6C647"
|26
|15511210043330985984000000
|0
|- style="background-color:#E6C647"
|27
|403291461126605635584000000
|0
|- style="background-color:#E6C647"
|28
|10888869450418352160768000000
|0
|- style="background-color:#94DCF2"
|29
|304888344611713860501504000000
|28
|- style="background-color:#E6C647"
|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'' [[teorija izračunljive kompleksnosti|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 {{Brez preloma|1=''p'' = 2''m'' + 1}} se lahko preoblikuje levo stran kongruence:

: <math> 1\cdot 2\cdots (p-1)\ \equiv\ -1\ \pmod{p} \!\, , </math>

da se dobi kongruenco:

: <math> 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} \!\, . </math>

To postane:

: <math> \prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1} \pmod{p} \!\, , </math>

ali:

: <math> (m!)^2 \equiv(-1)^{m+1} \pmod{p} \!\, . </math>

To dejstvo se lahko uporabi za dokaz dela slavnega rezultata: za katerokoli praštevilo ''p'', za katerega velja [[pitagorejsko praštevilo|''p''&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;4)]], je število (−1) kvadrat ([[kvadratni ostanek]]) mod ''p''. Predpostavi se, da je ''p''&nbsp;=&nbsp;4''k''&nbsp;+&nbsp;1 za neko celo število ''k''. Potem se lahko vzame ''m''&nbsp;=&nbsp;2''k'' zgoraj in sklepa, da je (''m''!)<sup>2</sup> kongruentno (−1).

=== Formule praštevil ===

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

=== p-iška funkcija gama ===<!-- Praštevilski številski sistem (10-iški, 2-iški, p-iški). -->

Wilsonov izrek se uporablja za definiranje [[p-iška funkcija gama|p-iške funkcije gama]].

== Gaussova posplošitev ==

[[Carl Friedrich Gauss|Gauss]] je dokazal, da velja:<ref>Gauss, DA, art. 78</ref>

: <math>
\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}
</math>

kjer predstavlja ''p'' liho praštevilo in <math>\alpha</math> naravno število. Vrednosti od ''m'' za produkt −1 so tiste, kjer je [[primitivni koren modula n|primitivni koren modula ''m'']].

To se še naprej posploši v dejstvo, da je v katerikoli [[končna grupa|končni]] [[Abelova grupa|Abelovi grupi]] ali produkt vseh elementov identiteta ali je natanko eden element ''a'' [[red (teorija grup)|reda]] 2 (a ne oboje). V zadnjem primeru, je produkt vseh elementov enak ''a''

== Glej tudi ==

* [[Wilsonovo praštevilo]]
* [[tabela kongruenc]]

== Sklici ==

{{sklici|3}}

== Viri ==

{{refbegin}}
''[[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.
*{{Citation
 | last1 = Gauss
 | first1 = Carl Friedrich
 | last2 = Clarke
 | first2 = Arthur A.
 | title = Disquisitiones Arithemeticae
 | edition=2. corrected
 | publisher = [[Springer Science+Business Media|Springer]]
 | location = New York
 | year = 1986
 | isbn = 0-387-96254-9
 | postscript = &nbsp;(translated into English)
}}.
*{{Citation
 | last1 = Gauss
 | first1 = Carl Friedrich
 | last2 = Maser
 | first2 = H.
 | title = Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory)
 | edition=2.
 | publisher = Chelsea
 | location = New York
 | year = 1965
 | isbn = 0-8284-0191-8
 | postscript = &nbsp;(translated into German)
}}.
*{{Citation
 | last = Landau
 | first = Edmund
 | title = Elementary Number Theory
 | publisher = Chelsea
 | location = New York
 | year = 1966
}}.
*{{navedi knjigo
 | last = Ore
 | first = Oystein
 | author-link = Oystein Ore
 | title = Number Theory and its History
 | publisher = Dover
 | year = 1988
 | pages = [https://archive.org/details/numbertheoryitsh0000orey/page/259 259–271]
 | isbn = 0-486-65620-9
 | url = https://archive.org/details/numbertheoryitsh0000orey/page/259
 }}
{{refend}}

== Zunanje povezave ==

* {{springer|title=Wilson theorem|id=p/w098010}}
* {{Mathworld|urlname=WilsonsTheorem|title=Wilson's Theorem}}
* Dokaz v [[sistem Mizar|sistemu Mizar]]: http://mizar.org/version/current/html/nat_5.html#T22

[[Kategorija:Modularna aritmetika]]
[[Kategorija:Izreki teorije števil]]