Wilson-tétel

A Wilson-tétel a következőt állítja: ha p prímszám, akkor

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

Összetett számra ez nem teljesülhet, mivel, ha n>1 összetett, akkor n-nek és (n-1)!-nak van közös osztója, sőt, minden 4-nél nagyobb n összetett számra

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

Így ez a tétel elméletben használható lenne prímtesztnek, de gyakorlatilag $n-2$ szorzás elvégzésével jár, így a tipikusan legalább pár száz jegyből álló számoknál nem praktikus.

Az angol John Wilson, Edward Waring tanítványa fedezte fel. Waring 1770-ben bejelentette a tételt, de bizonyítani nem tudta. Lagrange adta az első bizonyítást 1773-ban. Minden jel szerint már Leibniz ismerte a tételt, de nem publikálta.

A tételt úgy is általánosíthatjuk tetszőleges modulusra, hogy a redukált maradékosztályok szorzatát vizsgáljuk. Ha ezt Π(n)-nel jelöljük, akkor Π(n) ≡ -1 mod n, ha n=4, páratlan prímhatvány, vagy páratlan prímhatvány kétszerese, a többi esetben Π(n) ≡ 1 mod n.

Bizonyításai

1. bizonyítás

Feltesszük, hogy p>2. Minden x redukált maradékosztályhoz van egy és csak egy y redukált maradékosztály, hogy xy≡ 1 mod p. Ezzel párokra osztom a redukált maradékosztályokat, csak akkor van baj, amikor egy maradékosztály önmagának a párja, azaz x²≡ 1 mod p. Tehát a redukált maradékrendszert fel tudom bontani a következőképpen: 1,-1, és párok, amiknek a szorzata az 1 maradékot adja. Ezeket összeszorozva a -1 maradékot kapjuk.

2. bizonyítás

Feltehetjük, hogy p>2. A modulo p test fölött vegyük a következő polinomot:

$x^{p-1}-1-(x-1)\cdots(x-p+1).$

Ez a kis Fermat-tétel miatt 0 az 1,…,p-1 maradékosztályok mindegyikére, viszont fokszáma legfeljebb p-2, mert a két x^p-1-s tag kiejti egymást. Test feletti polinomok között csak az azonosan 0 polinomnak lehet több gyöke, mint a fokszáma, ez tehát az azonosan 0 polinom. Tehát konstans tagja is nulla, ami (mivel p páratlan) $-1-(p-1)!$.

3. bizonyítás

Tegyük fel, hogy p>2. Legyen $g$ primitív gyök modulo p (ismert, hogy ilyen létezik). Ekkor $(p-1)! \equiv \prod _{k=1}^{p-1}g^k \pmod {p}$ , hiszen $g$-nek p-1 egymásutáni hatványa redukált maradékrendszert alkot modulo p. Így $(p-1)!\equiv\prod _{k=1}^{p-1}g^k=g^{\frac {p(p-1)}{2}} \equiv g^{\frac {p-1}2} \equiv -1 \pmod {p}$, itt használtam, hogy p páratlan prím, továbbá, hogy $g^{\frac {p-1}2}\equiv -1 \pmod {p}$, mert 1 nem lehet, mert g primitív gyök, de négyzete $1 \pmod {p}$ a kis Fermat-tétel miatt, így csak $-1$ lehet.