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.

∎