youproof.orgDeep Math. Human Access.

Bizonyítás

Tekintsünk egy tetszőleges R=\{r_1; r_2; \ldots; r_{\varphi(m)}\} modulo m redukált maradékrendszert. Mivel a relatív prím m-hez, ezért a 20.19. Tétel 2. pontja alapján az S=\{ar_1; ar_2; \ldots; ar_{\varphi(m)}\} számhalmaz is egy modulo m 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 S halmazban minden ar_i elemnek van egy r_j párja az R halmazban, amely ugyanannak a redukált maradékosztálynak a reprezentánseleme, vagyis vele kongruens modulo m. Most átmenetileg nevezzük át az R elemeit úgy, hogy az ar_i ilyen értelemben vett párját jelöljük s_i-vel.

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

\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 \varphi(m) darab kongruencia összeszorozható egymással:

\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 R halmaz elemei szerepelnek, csak épp átmenetileg az s_1, s_2, ..., 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^{\varphi(m)} \cdot r_1r_2\ldots r_{\varphi(m)} \equiv r_1r_2\ldots r_{\varphi(m)} \pmod m

Mivel az R=\{r_1; r_2; \ldots; r_{\varphi(m)}\} számhalmaz egy modulo m redukált maradékrendszer, ezért a 20.17. Tétel 2. pontja alapján minden eleme relatív prím m-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^{\varphi(m)} \equiv 1\pmod m

∎