Wilson-tétel

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

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

${\displaystyle (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

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

Így ez a tétel elméletben használható lenne prímtesztnek, de gyakorlatilag ${\displaystyle 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.^[1]

A tételt úgy is általánosíthatjuk tetszőleges modulusra, hogy a redukált maradékosztályok szorzatát vizsgáljuk: ilyenkor a szorzat -1 maradékot ad a modulusra nézve, ha az 4, egy páratlan prímhatvány, vagy egy páratlan prímhatvány kétszerese; minden más esetben a keresett maradék értéke 1.

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:

${\displaystyle 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) ${\displaystyle -1-(p-1)!}$.

3. bizonyítás

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

A tétel általánosítása

Gauss általánosította a tételt a következő módon.^[2] Legyen Π(n) a modulo n redukált maradékrendszer elemeinek szorzata, ekkor Π(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.

Az általánosítás bizonyítása természetes módon átvihető az előbbi 1. bizonyításból:

Világos, hogy minden redukált x maradékosztályhoz pontosan egy olyan y redukált maradékosztály van, amelyre xy ≡ 1 (mod n). Lesznek olyan x maradékosztályok, melyekre x és y különbözik egymástól, ezek a maradékosztályok tehát olyan párokba rendezhetők, melyeknek szorzata modulo n éppen 1 lesz. Vagyis az összes ilyen maradékosztály szorzata is 1-et ad modulo n.

Itt azokat a maradékosztályokat hagytuk ki, melyekre x=y, vagyis x² ≡ 1 mod n. Ezeknél a maradékosztályoknál párosítsuk össze az x és n-x maradékosztályokat (ezek különbözők, hisz n>2), ez azért hasznos számunkra, mert x(n-x) ≡ -x² ≡ -1 mod n. Már csak az a feladat, hogy számoljuk össze ezen maradékosztályokat.

Írjuk fel n prímfelbontását: legyen ${\displaystyle n=p_{1}^{\alpha _{1}}\dots p_{k}^{\alpha _{k}}}$. Ekkor a kínai maradéktétel szerint x² ≡ 1 mod n ekvivalens azzal, hogy ${\displaystyle x^{2}\equiv 1\mod p_{i}^{\alpha _{i}}}$ teljesül minden i=1,...,k-ra. Ez pontosan kétféle lehetőséget ad x maradékára modulo ${\displaystyle p_{i}^{\alpha _{i}}}$, ha ${\displaystyle p_{i}\geq 3}$, hiszen a kongruencia ekvivalens a ${\displaystyle p_{i}^{\alpha _{i}}|x^{2}-1=(x+1)(x-1)}$ oszthatósággal, ahol a két tényező közül legfeljebb egy lehet ${\displaystyle p_{i}}$-vel osztható, vagyis a kongruencia két megoldása ${\displaystyle x\equiv \pm 1\mod p_{i}^{\alpha _{i}}}$. Modulo egy kettőhatvány kicsit más a helyzet: ha ${\displaystyle 2^{\alpha }|(x+1)(x-1)}$, akkor mindkét tényező páros lesz: egyik 4-gyel osztható, a másik nem. Az ${\displaystyle \alpha =1,2}$ esetekben rendre 1 és 2 megoldása van a kongruenciának, ám ${\displaystyle \alpha \geq 3}$-ra már 4 megoldása van a kongruenciának modulo ${\displaystyle 2^{\alpha }}$, hiszen csak ${\displaystyle 2^{\alpha -1}|x\pm 1}$-nek kell fennállnia.

Ha az x² ≡ 1 mod n kongruencia megoldásszáma 4-gyel osztható, akkor páros sok ${\displaystyle x\leftrightarrow n-x}$ pár jön létre, így a redukált maradékrendszer elemeinek szorzata 1 lesz, ha pedig nem, akkor -1 a szorzat. A megoldásszámot pedig megkaphatjuk, ha összeszorozzuk minden i=1,...,k-ra az ${\displaystyle x^{2}\equiv 1\mod p_{i}^{\alpha _{i}}}$ megoldásszámát, hisz az modulo az egyes prímhatványok egymástól függetlenül választhatjuk meg x maradékát. Ebből leolvasható, hogy a szorzat 1, ha legalább két 2-nél nagyobb prímtényezője van n-nek, illetve ha osztható 4-gyel és 4-nél nagyobb, továbbá ha nem osztható 4-gyel és legfeljebb egy 2-nél nagyobb prímtényezője van, vagy ha n=4, akkor a szorzat -1 lesz: ezt akartuk belátni.

Jegyzetek