Wilsonova veta

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Wilsonova veta je veta v teórii čísel, ktorá hovorí, že prirodzené číslo n > 1 je prvočíslo práve vtedy, keď

(n-1)!\ \equiv\ -1 \pmod n.

História[upraviť | upraviť zdroj]

Veta bola prvý raz publikovaná v roku 1770 Edwardom Waringom a pripisuje sa jeho študentovi Johnovi Wilsonovi, ani jeden z nich však neuviedol jej dôkaz.[1] Navyše Waring publikoval vetu len v tvare nutnej podmienky. Prvý raz bola veta dokázaná (už v tvare ekvivalencie) Josephom Louisom Lagrangom v roku 1773.[1]

Príklad[upraviť | upraviť zdroj]

V nasledujúcej tabuľke sú uvedené hodnoty n 2-30, (n-1)!, A zvyšok po (n-1)! je rozdelený n. (Zvyšok po m delí n je napísaný m mod n). Farba pozadia je ružová na hlavných hodnotách n, svetlo zelené pre kompozitné hodnoty.

Tabuľka zvyškom 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

Dôkaz[2][upraviť | upraviť zdroj]

Ľahko je možné overiť, že tvrdenie platí pre n = 2 a n = 3. Predpokladajme teda, že n > 3. Ak je n zložené číslo, jeho celočíselné delitele patria do množiny M = \{1,2,\ldots,n-1\}, a teda najväčší spoločný deliteľ čísel n a (n-1)! je väčší ako nula, a preto neplatí (n-1)!\ \equiv\ -1 \pmod n.. Nech je teda n prvočíslo. Potom je každé číslo z množiny M nesúdeliteľné s n, z čoho vyplýva, že pre každé číslo a z M existuje číslo b z M tak, že

ab \equiv 1\ (\text{mod } n).

Navyše, b je určené jednoznačne a keďže je n prvočíslo, a = b práve vtedy, keď a = 1 alebo a = n-1. Navyše, tieto dvojice (okrem tých, kde a = 1 a a = n-1) je možné popárovať tak, že každé číslo sa nachádza len v jednej dvojici. Vynásobením týchto dvojíc dostávame kongruenciu

2\cdot 3 \cdot \ldots \cdot (n-2) \equiv 1\ (\text{mod } n),

z čoho vynásobením (n-1) vyplýva požadované tvrdenie.

Referencie[upraviť | upraviť zdroj]

  1. a b Yan, S. Y.: Number Theory for Computing. 2. vydanie, Springer, 2002.
  2. A proof of Wilson's Theorem.

Externé odkazy[upraviť | upraviť zdroj]