Stelling van Wilson

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

De stelling van Wilson is een wiskundige stelling die zegt dat wanneer

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

p een priemgetal is.

De omgekeerde bewering is ook waar: voor een priemgetal p geldt: (p-1)! ≡ -1 mod p. Deze gelijkheid: (p-1)! ≡ -1 mod p, kan ook worden geformuleerd als: (p - 1)! + 1 is door p te delen.

De stelling werd het eerst ontdekt door Ibn al-Haytham, ook bekend als Alhazen, maar is naar John Wilson genoemd. Wilson was een student van Edward Waring. Die formuleerde de stelling in 1770, maar noch hijzelf noch Wilson konden de stelling bewijzen. Lagrange gaf het eerste bewijs in 1773. Leibniz kende de stelling een eeuw eerder ook, maar publiceerde die niet.

Voor de notaties ! faculteit en ≡ congruent zie aldaar.


Bewijs[bewerken]

Uit het ongerijmde: stel dat (p - 1)! + 1 door p is te delen en dat p weer door een getal d met 1 < d < p is te delen. Omdat d een van de getallen 2, 3, ..., p-1 is, is (p − 1)! door p te delen. (p − 1)! + 1 is ook door d te delen, dus is 1 ook door d te delen. d=1 is in tegenspraak met de veronderstelling.

Omgekeerd[bewerken]

eerste bewijs

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. 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.

tweede bewijs

Stel p is een priemgetal groter dan 2. Beschouw de polynomen

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

en

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

De constante van f(x) is (p - 1)! + 1.

f(x) is een polynoom, waarvan de graad ten hoogste p − 2 is, met dus ten hoogste p - 2 nulpunten, mod p geldt hetzelfde. 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) = 0 mod p, oftewel tenzij iedere coëfficiënt van f(x) door p is te delen, de constante (p − 1)! + 1 dus ook.

Samengestelde getallen[bewerken]

Voor samengestelde getallen n > 5 geldt een andere gelijkheid:

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

voor samengestelde getallen is (n−1)! door n te delen.

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


Algemene vorm van de stelling[bewerken]

Een algemene vorm 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 met volledige inductie is te bewijzen.

Van Gauss is de volgende vorm 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{voor } m=4,\;p^\alpha,\;2p^\alpha \\ \ \ 1\ \mbox{mod }m & \mbox{anders} \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