youproof.orgDeep Math. Human Access.

Bizonyítás

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

Visszafelé: Tegyük fel, hogy az SS halmaz mm 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 mm, ezért mm darab maradékosztályt reprezentálnak, azaz a 20.4. Tétel alapján az összeset. Az SS halmaz tehát valóban egy modulo mm teljes maradékrendszer.

A 2. állítás: Tegyük fel, hogy SS egy modulo mm redukált maradékrendszer. Mivel a modulo mm redukált maradékosztályok száma a 20.7. Definíció alapján φ(m)\varphi(m), és SS minden redukált maradékosztályból pontosan egy elemet tartalmaz, ezért elemszáma szükségképpen φ(m)\varphi(m). Továbbá SS elemei páronként inkongruensek modulo mm, hiszen mindegyik különböző redukált maradékosztályból származik. Végül SS minden eleme relatív prím mm-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 mm-hez.

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

∎