Bizonyítás

A 18.3. Definíció utáni megjegyzés 5. pontja alapján a $\bmod_m$ maradékképző függvény a $0$, $1$, $2$, ..., $m-1$ egész számokhoz mind különböző modulo $m$ maradékot rendel. Így a 20.1. Tétel 1. pontja alapján ezek a számok páronként inkongruensek. Továbbá, mivel a számuk épp $m$, ezért a 20.17. Tétel 1. pontja alapján ők egy modulo $m$ teljes maradékrendszert alkotnak.

Mivel ez egy teljes maradékrendszer, ezért tartalmazza egy-egy reprezentánsát minden modulo $m$ maradékosztálynak, így a redukált maradékosztályoknak is. Ez utóbbiak viszont biztosan mind relatív prímek $m$-hez, hiszen az általuk reprezentált redukált maradékosztályok a 20.17. Tétel 2. pontja alapján csupa $m$-hez relatív prím elemekből állnak.

A 20.7. Definíció szerint az Euler-féle $\varphi$-függvény a modulo $m$ redukált maradékosztályok számát adja meg. A fentiek alapján ez a szám valóban meg fog egyezni azon egészek számával, amelyek $0$, $1$, $2$, ..., $m-1$ teljes maradékrendszer elemei közül relatív prímek $m$-hez.

∎