youproof.orgDeep Math. Human Access.

Bizonyítás

Tekintsünk egy tetszőleges R={r1;r2;…;rφ(m)}R=\{r_1; r_2; \ldots; r_{\varphi(m)}\} modulo mm redukált maradékrendszert. Mivel aa relatív prím mm-hez, ezért a 20.19. Tétel 2. pontja alapján az S={ar1;ar2;…;arφ(m)}S=\{ar_1; ar_2; \ldots; ar_{\varphi(m)}\} számhalmaz is egy modulo mm redukált maradékrendszer.

Ez a 20.16. Definíció szerint azt jelenti, hogy mindkét számhalmaz tartalmaz egy-egy reprezentánselemet az összes létező redukált maradékosztályból. Tehát az SS halmazban minden ariar_i elemnek van egy rjr_j párja az RR halmazban, amely ugyanannak a redukált maradékosztálynak a reprezentánseleme, vagyis vele kongruens modulo mm. Most átmenetileg nevezzük át az RR elemeit úgy, hogy az ariar_i ilyen értelemben vett párját jelöljük sis_i-vel.

Ebből tehát φ(m)\varphi(m) darab kongruenciát lehet felírni, ahol a baloldalon az SS, míg a jobboldalon – a most bevezetett jelölésekkel – az RR halmaz elemei szerepelnek:

ar1≡s1(modm)ar2≡s2(modm)ar3≡s3(modm)⋮arφ(m)≡sφ(m)(modm)\begin{aligned} ar_1&\equiv s_1\pmod m \\ ar_2&\equiv s_2\pmod m \\ ar_3&\equiv s_3\pmod m \\ &\vdots \\ ar_{\varphi(m)}&\equiv s_{\varphi(m)}\pmod m \end{aligned}

A 20.2. Tétel 4. alapján ez a φ(m)\varphi(m) darab kongruencia összeszorozható egymással:

aa…a⏟φ(m) darab⋅r1r2…rφ(m)≡s1s2…sφ(m)(modm)\underbrace{aa \ldots a}_{\varphi(m)\ \text{darab}} \cdot r_1r_2\ldots r_{\varphi(m)} \equiv s_1s_2\ldots s_{\varphi(m)} \pmod m

A jobboldalon tehát az RR halmaz elemei szerepelnek, csak épp átmenetileg az s1s_1, s2s_2, ..., sφ(m)s_{\varphi(m)} nevekkel láttuk el őket. Az eredeti neveikkel szerepeltetve és az eszerinti indexelés alapján sorbarendezve őket az előbbi kongruencia tulajdonképpen így néz ki:

aφ(m)⋅r1r2…rφ(m)≡r1r2…rφ(m)(modm)a^{\varphi(m)} \cdot r_1r_2\ldots r_{\varphi(m)} \equiv r_1r_2\ldots r_{\varphi(m)} \pmod m

Mivel az R={r1;r2;…;rφ(m)}R=\{r_1; r_2; \ldots; r_{\varphi(m)}\} számhalmaz egy modulo mm redukált maradékrendszer, ezért a 20.17. Tétel 2. pontja alapján minden eleme relatív prím mm-hez. Emiatt a fenti kongruenciát a 20.3. Tétel utáni megjegyzés alapján ezekkel az elemekkel mind egyszerűsíthetjük, megkapva így a tétel állítását:

aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1\pmod m

∎