Stelling van Wilson

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De stelling van Wilson is een wiskundige stelling die zegt dat voor een priemgetal p geldt:

(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p).

Dit laatste kan ook geformuleerd worden als: (p - 1)! + 1 is deelbaar door p.

(Voor de notaties ! (faculteit) en ≡ (congruent) zie aldaar.)

De omgekeerde bewering is ook waar:

Als voor een getal p geldt:

(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p),

dan is p een priemgetal.

Historie[bewerken]

De stelling werd eerst ontdekt door Ibn al-Haytham (ook bekend als Alhazen), maar is vernoemd naar John Wilson (een student van de Engelse wiskundige Edward Waring) die het ruim 700 jaar later herontdekte. Waring kondigde de stelling aan in 1770, hoewel hij noch Wilson hem konden bewijzen. Lagrange gaf het eerste bewijs in 1773. Er is bewijs dat Leibniz de stelling een eeuw eerder ook kende, maar nooit publiceerde.

Bewijzen[bewerken]

Eerste bewijs[bewerken]

Dit bewijs gebruikt dat voor een priemgetal p > 2, de verzameling G = {1, 2, ... p − 1} een groep is onder vermenigvuldiging modulo p. Dit betekent dat voor ieder element a in G, er een uniek inverse element b in G is zodat ab ≡ 1 (mod p). Als ab (mod p), dan is a2 ≡ 1 (mod p), waaruit volgt a2 − 1 = (a + 1)(a − 1) ≡ 0 (mod p), en omdat p een priemgetal is, volgt a ≡ 1 of −1 (mod p), oftewel a = 1 of a = p − 1.

Met andere woorden, 1 en p − 1 zijn hun eigen inverse, maar ieder ander element van G heeft een verschillende inverse, en als we dus alle elementen van G paarsgewijs bij elkaar nemen op deze manier en allemaal met elkaar vermenigvuldigen, krijgen we modulo p het product −1. Bijvoorbeeld, als p = 11, krijgen we

10! = 1(10)(2 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8) \ \equiv\ -1\ (\mbox{mod}\ 11)

Als p = 2, is het resultaat eenvoudig te controleren.

Omgekeerd: stel dat (p - 1)! + 1 deelbaar is door p en dat p een zuivere deler d met 1 < d < p heeft. Omdat d een van de getallen 2, 3, ..., p-1 is, is d deler is van (p − 1)!. Maar d deelt ook (p − 1)! + 1, zodat d ook 1 deelt, wat een tegenspraak oplevert.

Tweede bewijs[bewerken]

Stel p is een priemgetal ongelijk aan 2. Beschouw de veelterm

g(x)=(x-1)(x-2) \cdots (x-(p-1))

en laat

f(x)=g(x)-(x^{p-1}-1)\,,

zodat f(x) een veelterm is van ten hoogste de graad p − 2, met dus ten hoogste p - 2 nulpunten. Reducerend mod p, zien we dat f(x) ten hoogste p − 2 wortels mod p heeft. Maar volgens de stelling van Fermat is ieder van de getallen 1,2, ...,p − 1 een nulpunt van f(x). Dit is onmogelijk, tenzij f(x) gelijk is aan nul mod p, oftewel tenzij iedere coëfficiënt van f(x) een deler is van p. En omdat p oneven is, is de constante term van f(x) gelijk aan (p − 1)! + 1, en volgt het resultaat.

Generalisaties[bewerken]

Een veralgemenisering is voor ieder oneven priemgetal p en voor ieder positief geheel getal k kleiner dan p:

(k-1)!(p-k)!\ \equiv\ (-1)^k\ (\mbox{mod}\ p)

hetgeen eenvoudig met volledige inductie is te bewijzen.

Van Carl Friedrich Gauss is een veralgemenisering van de stelling bekend:

\prod_{\begin{matrix} 1 \le a < m \\ (a,m)=1 \end{matrix}} 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.

waarin p een oneven priemgetal is.

Voorbeeld[bewerken]

De volgende tabel toont de waarden van n van 2 tot 30, (n -1)! en (n -1)! mod n. Als n een priemgetal is, dan is de achtergrondkleur roze. En als n een samengesteld getal is, dan is de achtergrondkleur lichtgroen.

Tabel van rest modulo n
n (n-1)! (n-1)!\ \bmod\ n
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

Omgekeerde[bewerken]

De stelling van Wilson roept de vraag op hoe het dan zit met een samengesteld getal n. Voor n > 5 geldt:

(n-1)! \equiv 0\ (\mbox{mod}\ n),

dus n is deler van (n−1)! .

Voor n = 4 geldt dit niet: (n−1)! = 3! ≡ 2 (mod 4).

Daarmee kan van een getal n > 4 vastgesteld worden of het al dan niet een priemgetal is, door na te gaan of het een deler is van (n−1)!.