Bizonyítás
A \varphi(ab) azon ab-nél nemnagyobb pozitív egészeknek a számával egyezik meg, amelyek ab-hez relatív prímek. A 20.12. Következmény alapján bármilyen tetszőleges egész szám akkor és csak akkor relatív prím ab-hez, ha relatív prím a-hoz is és b-hez is.
A \varphi(ab) érték kiszámításához tehát azokat az ab-nél nemnagyobb pozitív egészeket kell megszámlálnunk, amelyek relatív prímek a-hoz is és b-hez is. Ezt a következő lépésekben fogjuk megtenni:
- Összegyűjtjük az összes a-hoz relatív prím egész számot.
- Ezek közül kiválasztjuk azokat, amelyek 0 és ab közé esnek.
- Végül a maradékból kiválogatjuk azokat, amelyek b-hez is relatív prímek.
1. lépé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.
A 20.4. Tétel alapján e maradékosztályok elemei – és csak azok – kifejezhetők az r_1, r_2, ..., r_{\varphi(a)} reprezentánselemek segítségével az alábbi táblázat szerint, ahol minden oszlop egy-egy redukált maradékosztálynak felel meg:
2. lépés
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.
Ezt ugyanis behelyettesítve az egyenlőtlenségbe, valamint kihasználva a 15.11. Definíció szerinti 1. rendezési axiómát, az alábbi adódik:
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.
Másrészt viszont a k=b érték már nem megfelelő, ha ugyanis ezt helyettesítjük be az egyenlőtlenségbe, akkor az alábbit kapjuk:
Ez az egyenlőtlenség már nem teljesül, hiszen az r_i-t pozitívnak választottuk. Az 1. lépésben keletkezett táblázatból tehát az alábbi rész maradt meg, a többit kidobáltuk:
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.
3. lépés
Ez tehát egy \varphi(a) oszlopból álló táblázat, és minden oszlopban b darab szám van. Tekintsük például az i-edik oszlopot. Ennek elemei a következők:
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.
Összefoglalva: Összesen tehát \varphi(a)\cdot \varphi(b) darab olyan 0 és ab közötti egész szám létezik, amely relatív prím a-hoz is és b-hez is. Ezek száma a bizonyítás elején közölt észrevétel alapján megegyezik azon 0 és ab közötti egészek számával, amelyek relatív prímek ab-hez. Ezek száma viszont a 20.18. Következmény alapján \varphi(ab), így tehát valóban teljesül a tétel állítása:
∎