|
Mtematiikassa Wilsonin lauseen mukaan ''p'' on alkuluku jos ja vain jos
In [[mathematics]], '''Wilson's theorem''' states that ''p'' is a [[prime number]] [[if and only if]]
:<math>(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)</math>
.
(see [[factorial]] and [[modular arithmetic]] for the notation).
Lauseen keksi ensimmäisenä [[Ibn al-Haytham]] (tunnetaan myös nimellä '''Alhazen'''), mutta se on nimetty [[John Wilson (matemaatikko)|John Wilsonin]] mukaan, joka keksi tuloksen yli 700 vuotta myöhemmin. Waring julkaisi tuloksen vuonna 1770, vaikka hän ja Wilson eivät kyenneet todistamaan lausetta. [[Joseph Louis Lagrange|Lagrange]] antoi ensimmäisen todistuksen vuonnaa 1773. Liebniz tunsi myös tuloksen vuosikymmenen aikaisemmin, mutta ei koskaan julkaissut todistusta.
== Todistus==
The theorem was first discovered by [[Ibn al-Haytham]] (also known as '''Alhazen'''), but it is named after [[John Wilson (mathematician)|John Wilson]] (a student of the English [[mathematician]] [[Edward Waring]]) who rediscovered it more than 700 years later. Waring announced the theorem in 1770, although neither he nor Wilson could prove it. [[Joseph Louis Lagrange|Lagrange]] gave the first proof in 1773. There is evidence that [[Gottfried Leibniz|Leibniz]] was also aware of the result a century earlier, but he never published it.
This proof uses the fact that ifJos ''p'' ison anpariton odd primealkuluku, then the set of numbersjoukko ''G'' = ('''Z'''/''p'''''Z''')<sup>×</sup> = {1, 2, ... ''p'' − 1} formsmuodostaa a [[group_(mathematics)|group]]multiplikatiivisen underryhmän [[ modular arithmetickongruenssi| multiplication modulo ''p'']] suhteen. ThisTällöin means that for each elementkaikilla '' aG'' :n inalkioilla '' Ga'' , thereon isolemassa a unique [[inverse element|inverse]]yksikäsitteinen elementkäänteisalkio ''b'' , in ''G'' such thatjolle ''ab'' ≡ 1 (mod ''p'') . ja joka on siis myös ''G'':n alkio. IfJos ''a'' ≡ ''b'' (mod ''p''), thenon ''a''<sup>2</sup> ≡ 1 (mod ''p''), which forcesjolloin ''a''<sup>2</sup> − 1 = (''a'' + 1)(''a'' − 1) ≡ 0 (mod ''p''), andja sincekoska ''p'' ison primealkuluku, thison forcesoltava ''a'' ≡ 1 ortai −1 (mod ''p''), i.e.joten ''a'' = 1 ortai ''a'' = ''p'' − 1. ▼== Proofs==
Toisin sanoen 1 ja ''p'' − 1 ovat toistensa käänteisalkiota, mutta kaikille muille ''G'':n alkioille on olemassa toinen käänteisalkio, joten ryhmittelemällä tulon tekijät huomataan, että tuloksi tulee −1. Jos ''p''=2 on helppo nähdä, että Wilsonin lause on voimassa
=== First proof ===
Toisaalta olkoon kongruenssirelaatio voimassa [[yhdistetty luku|yhdistetylle luvulle]] ''n''. Tällöin ''n'':llä ön aito tekijä ''d'', 1<''d''<''n''. Selvästi ''d'' jakaa (''n'' − 1)!. Mutta kongruenssin perusteella ''d'' jakaa muös luvun (''n'' − 1)! + 1, joten ''d'' jakaa ykkösen, mikä on ristiriita.
▲This proof uses the fact that if ''p'' is an odd prime, then the set of numbers ''G'' = ('''Z'''/''p'''''Z''')<sup>×</sup> = {1, 2, ... ''p'' − 1} forms a [[group_(mathematics)|group]] under [[modular arithmetic|multiplication modulo ''p'']]. This means that for each element ''a'' in ''G'', there is a unique [[inverse element|inverse]] element ''b'' in ''G'' such that ''ab'' ≡ 1 (mod ''p''). If ''a'' ≡ ''b'' (mod ''p''), then ''a''<sup>2</sup> ≡ 1 (mod ''p''), which forces ''a''<sup>2</sup> − 1 = (''a'' + 1)(''a'' − 1) ≡ 0 (mod ''p''), and since ''p'' is prime, this forces ''a'' ≡ 1 or −1 (mod ''p''), i.e. ''a'' = 1 or ''a'' = ''p'' − 1.
[[Luokka:Lukuteoria]]
In other words, 1 and ''p'' − 1 are each their own inverse, but every other element of ''G'' has a distinct inverse, and so if we collect the elements of ''G'' pairwise in this fashion and multiply them all together, we get the product −1. For example, if ''p'' = 11, we have
:<math>10! = 1(10)(2 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8) \ \equiv\ -1\ (\mbox{mod}\ 11).\,</math>
If ''p'' = 2, the result is trivial to check.
For a converse (but see below for a more exact converse result), suppose the [[congruence relation|congruence]] holds for a [[composite number|composite]] ''n'', and note that then ''n'' has a proper [[divisor]] ''d'' with 1 < ''d'' < ''n''. Clearly, ''d'' [[divides]] (''n'' − 1)! But by the congruence, ''d'' also divides (''n'' − 1)! + 1, so that ''d'' divides 1, a contradiction.
=== Second proof ===
Here is another proof of the first direction: Suppose ''p'' is an odd prime. Consider the polynomial
:<math>g(x)=(x-1)(x-2) \cdots (x-(p-1)).\,</math>
Recall that if ''f''(''x'') is a nonzero polynomial of degree ''d'' over a [[field (mathematics)|field]] ''F'', then ''f''(''x'') has at most ''d'' roots over ''F''. Now, with ''g''(''x'') as above, consider the polynomial
:<math>f(x)=g(x)-(x^{p-1}-1).\,</math>
Since the leading coefficients cancel, we see that ''f''(''x'') is a polynomial of degree at most ''p'' − 2. Reducing mod ''p'', we see that ''f''(''x'') has at most ''p'' − 2 roots mod ''p''. But by [[Fermat's little theorem|Fermat's little theorem]], each of the elements 1, 2, ..., ''p'' − 1 is a root of ''f''(''x''). This is impossible, unless ''f''(''x'') is identically zero mod ''p'', i.e. unless each coefficient of ''f''(''x'') is divisible by ''p''.
But since ''p'' is odd, the constant term of ''f''(''x'') is just (''p'' − 1)! + 1, and the result follows.
== Applications ==
Wilson's theorem is useless as a [[primality test]], since computing (''n'' − 1)! is difficult for large ''n''.
Using Wilson's Theorem, we have for any prime ''p'':
:<math>1\cdot 2\cdots (p-1)\ \equiv\ -1\ (\mbox{mod}\ p)</math>
:<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\ (\mbox{mod}\ p)</math>
where ''p'' = 2''m'' + 1. This becomes
:<math>\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1}\ (\mbox{mod}\ p).</math>
And so primality is determined by the [[quadratic residue]]s of ''p''. We can use this fact to prove part of a famous result: −1 is a square (quadratic residue) mod ''p'' if ''p'' ≡ 1 (mod 4). For suppose ''p'' = 4''k'' + 1 for some integer ''k''. Then we can take ''m'' = 2''k'' above, and we conclude that
:<math>\left( \prod_{j=1}^{2k}\ j \right)^{2} = \prod_{j=1}^{2k}\ j^2\ \equiv (-1)^{2k+1}\ = -1(\mbox{mod}\ p).</math>
== Generalization ==
There is also a generalization of Wilson's theorem, due to [[Carl Friedrich Gauss]]:
:<math>\prod_{1 \le a < m \atop (a,m)=1} \!\!a \ \equiv \ \left \{ \begin{matrix} -1\ (\mbox{mod }m) & \mbox{if } m=4,\;p^\alpha,\;2p^\alpha \\ \ \ 1\ (\mbox{mod }m) & \mbox{otherwise} \end{matrix} \right. </math>
where ''p'' is an odd prime.
==Converse==
The converse to Wilson's theorem states that for a [[composite number]] ''n'' > 5,
:''n'' divides (''n'' − 1)!.
This leaves the case ''n'' = 4, for which 3! is congruent to 2 modulo 4.
In fact if ''q'' is a prime factor of ''n'', so that ''n'' = ''qa'', the numbers
:1, 2, ..., ''n'' − 1
include ''a'' − 1 multiples of ''q''. Therefore the power of ''q'' dividing the factorial is at least ''n/q'' − 1; and the power dividing ''n'' at most
:log ''n''/log ''q''.
The required inequality
:log ''n''/log ''q'' ≤ ''n/q'' − 1
does hold in general, except for the case ''q'' = 2 and ''n'' = 4.
[[Category:Modular arithmetic]]
[[Category:Prime numbers]]
[[Category:Factorial and binomial topics]]
[[Category:Mathematical theorems]]
[[bg:Теорема на Уилсън]]
| 