Bizonyítás

A 20.15. Tétel alapján az $a$-hoz relatív prímek pontosan a modulo $a$ redukált maradékosztályok elemei lesznek. Ilyenből a 20.7. Definíció alapján épp $\varphi(a)$ darab van. E $\varphi(a)$ darab modulo $a$ redukált maradékosztály mindegyikéből válasszuk ki a legkisebb pozitív elemet. Az így kapott $r_1$, $r_2$, ..., $r_{\varphi(a)}$ számok tehát reprezentálják az összes modulo $a$ redukált maradékosztályt.

Most minden olyan számot kidobálunk ebből a táblázatból, amely nem $0$ és $ab$ közé esik. Mivel az $r_1$, $r_2$, ..., $r_{\varphi(a)}$ reprezentánselemeket úgy választottuk ki, hogy minden oszlopban ők legyenek a legkisebb pozitív egészek, ezért a táblázat ezek fölötti sorait ki is hajíthatjuk, hiszen ott már csupa negatív szám szerepel. Kérdés, hogy a táblázatban lefelé meddig mehetünk el a $k$ paraméterrel úgy, hogy bármely $i$-edik oszlopban az $r_i+ka\lt ab$ egyenlőtlenség még éppen teljesüljön? A határvonal épp a $k=b-1$ érték lesz.

Ez viszont nyilvánvalóan teljesül, hiszen $r_i$-t úgy választottuk ki, hogy ő az egyik maradékosztály legkisebb pozitív eleme legyen. Minthogy a $0$, $1$, $2$, ..., $a-1$ számok az összes létező modulo $a$ maradékosztályt reprezentálják, ezért $r_i$ is szükségképpen közöttük van.

Ez a táblázat tehát tartalmazza az összes olyan $0$ és $ab$ közé eső egész számot, amely relatív prím $a$-hoz.

Vegyük észre, hogy ezt a számhalmazt úgy kaptuk, hogy a $\{0;1;2;\ldots;b-1\}$ számhalmaz minden elemét megszoroztuk $a$-val – ami ugye a tétel szövege alapján relatív prím $b$-hez –, majd az így kapott számokhoz hozzáadtunk $r_i$-t. Mivel azonban a $\{0;1;2;\ldots;b-1\}$ számhalmaz nem más, mint egy modulo $b$ teljes maradékrendszer, ezért a 20.19. Tétel alapján az újonnan kapott számhalmaz is az.

Mivel a táblázat minden oszlopa ugyanígy képződött, ezért a táblázat minden oszlopában tulajdonképpen egy-egy modulo $b$ teljes maradékrendszer áll. Minden oszlopban képviselve van tehát az összes modulo $b$ maradékosztály. Mivel ezek közül a redukált maradékosztályok száma az Euler-féle $\varphi$-függvény a 20.7. Definíciója alapján $\varphi(b)$, ezért ez egyben azt is jelenti a 20.18. Következmény alapján, hogy minden oszlopban $\varphi(b)$ darab olyan elem van, amely relatív prím $b$-hez. Minthogy a táblázatban az oszlopok száma $\varphi(a)$, így a táblázatnak összesen $\varphi(a)\cdot \varphi(b)$ eleme relatív prím $b$-hez is.