youproof.orgDeep Math. Human Access.

Bizonyítás

Először megmutatjuk, hogy a j_{\text{max}} kitevő mindig létezik. Egyrészt ugyanis legalább egy megfelelő j kitevő biztosan van, hiszen j=0 és x=-1 választással nyilván teljesül az alábbi kongruencia:

(\underbrace{-1}_{=x})^{2^{\overbrace{0}^{=j}}}\equiv -1\pmod n

Másrészt a szóba jövő kitevők a véges \{0;1;2;\ldots;e-1\} halmazból kerülnek ki, így közöttük létezik legnagyobb is.

Másodszor megmutatjuk, hogy a H_n halmaz jóldefiniált olyan értelemben, hogy egy benne lévő maradékosztályt bármelyik reprezentánselemével megadhatunk. Ha ugyanis a\equiv b\pmod n, akkor a 20.2. Tétel 6. pontja alapján teljesül az alábbi kongruencia is:

a^{2^{j_{\text{max}}}k}\equiv b^{2^{j_{\text{max}}}k}\pmod n

Így a baloldalon szereplő hatvány pontosan akkor kongruens \pm 1-gyel, ha a jobboldalon szereplő hatvány is.

Harmadszor megmutatjuk, hogy H_n minden eleme redukált maradékosztály. Legyen [a]_n a H_n halmaz egy tetszőleges eleme. Ekkor a tétel szövege szerint teljesül az alábbi kongruencia:

a^{2^{j_{\text{max}}}k}\equiv \pm 1\pmod n

Akár 1, akár -1 szerepel a jobboldalon, a kongruenciát a 20.2. Tétel 6. pontja alapján négyzetre emelve, majd a baloldalt a 24.11. Tétel 2. pontja alapján átírva a következőt kapjuk:

a^{2^{j_{\text{max}}+1}k}\equiv 1\pmod n

Találtunk tehát egy olyan pozitív kitevőt – nevezetesen 2^{j_{\text{max}}+1}k-t –, amelyre a-t emelve az eredmény 1-gyel kongruens modulo n. Ebből viszont a 20.21. Tétel alapján következik, hogy a relatív prím n-hez, azaz a 20.15. Tétel értelmében [a]_n valóban redukált maradékosztály, azaz

H_n \sube (\Z/n\Z)^{\times}

Végül megmutatjuk, hogy H_n részcsoport. Mivel (\Z/n\Z)^{\times} véges csoport, ezért a 24.14. Következmény értelmében elegendő azt megmutatni, hogy H_n nemüres, és zárt a csoportműveletre, azaz a maradékosztályok közötti szorzásra nézve.

Mivel 1^{2^{j_{\text{max}}}k}\equiv 1\pmod n, ezért a tétel szövege szerint az [1]_n \in H_n, tehát H_n valóban nemüres. Legyen most [a]_n és [b]_n a H_n halmaz két tetszőleges eleme. Ekkor a tétel szövege szerint teljesülnek az alábbi kongruenciák:

\begin{aligned} a^{2^{j_{\text{max}}}k}&\equiv \pm 1\pmod n \\ b^{2^{j_{\text{max}}}k}&\equiv \pm 1\pmod n \end{aligned}

A két kongruenciát a 20.2. Tétel 4. pontja alapján összeszorozhatjuk egymással, majd a baloldalt a 24.11. Tétel 1. pontja alapján átírhatjuk. Mivel 1 és -1 közül bármelyik kettőt összeszorozva ismét 1-et vagy -1-et kapunk, ezért:

(ab)^{2^{j_{\text{max}}}k}\equiv \pm 1\pmod n

Azt kaptuk tehát, hogy [ab]_n \in H_n. Minthogy az [ab]_n maradékosztály a 20.5. Tételben szereplő definíció szerint épp az [a]_n és [b]_n maradékosztályok szorzata, ezért H_n zárt a csoportműveletre nézve, és így valóban részcsoport (\Z/n\Z)^{\times}-ben.

∎