Bizonyítás

Az 1. állítás: Tegyük fel, hogy S egy modulo m teljes maradékrendszer. Mivel a modulo m maradékosztályok száma a 20.4. Tétel alapján m, és S minden maradékosztályból pontosan egy elemet tartalmaz, ezért elemszáma szükségképpen m. Továbbá S elemei páronként inkongruensek modulo m, hiszen mindegyik különböző maradékosztályból származik.

Visszafelé: Tegyük fel, hogy az S halmaz m darab páronként inkongruens számot tartalmaz. Ekkor a páronkénti inkongruencia miatt ezek mindegyike különböző maradékosztályokba tartozik. Továbbá mivel a számuk m, ezért m darab maradékosztályt reprezentálnak, azaz a 20.4. Tétel alapján az összeset. Az S halmaz tehát valóban egy modulo m teljes maradékrendszer.

A 2. állítás: Tegyük fel, hogy S egy modulo m redukált maradékrendszer. Mivel a modulo m redukált maradékosztályok száma a 20.7. Definíció alapján \varphi(m), és S minden redukált maradékosztályból pontosan egy elemet tartalmaz, ezért elemszáma szükségképpen \varphi(m). Továbbá S elemei páronként inkongruensek modulo m, hiszen mindegyik különböző redukált maradékosztályból származik. Végül S minden eleme relatív prím m-hez, hiszen ezeket redukált maradékosztályokból választottuk ki, márpedig a 20.15. Tétel alapján egy redukált maradékosztálynak minden eleme relatív prím m-hez.

Visszafelé: Tegyük fel, hogy az S halmaz \varphi(m) darab páronként inkongruens számot tartalmaz, amelyek mindegyike relatív prím m-hez. Ekkor a páronkénti inkongruencia miatt ezek mindegyike különböző maradékosztályokba tartozik, amelyek mindegyike az m-hez való relatív prímség miatt redukált maradékosztály. Továbbá mivel a számuk \varphi(m), ezért \varphi(m) darab redukált maradékosztályt reprezentálnak, azaz a 20.7. Definíció alapján az összeset. Az S halmaz tehát valóban egy modulo m redukált maradékrendszer.

∎