Bizonyítás

A 20.1. Tételben bevezetett modulo $m$ kongruencia ekvivalens az $I=(m)$ főideál szerinti kongruenciával. Ez utóbbi a 18.21. Tétel alapján valóban egy ekvivalenciareláció, így tehát a modulo $m$ kongruencia is az, továbbá pontosan ugyanazok lesznek a maradékosztályaik.

Ha $a$ egy tetszőleges egész szám, akkor az $a$-t tartalmazó modulo $I$ maradékosztály szintén a 18.21. Tétel alapján épp az $a+I$ halmaz lesz, ahol a $+$ szimbólum a 18.19. Definícióban bevezetett komplexusösszeadást jelöli. Ez a halmaz tehát meg fog egyezni az $a$-t tartalmazó modulo $m$ maradékosztállyal, ezért elég meghatároznunk az $a+I$ halmazt. Minthogy az $I=(m)$ főideál épp $m$ többszöröseit tartalmazza, ezért az $a+I$ halmaz valóban éppen a $km + a$ alakban felírható egész számokból áll. Speciálisan ha $m=0$, akkor ilymódon minden egész szám külön maradékosztályba kerül, így ezek száma valóban végtelen.

Ha $m\gt 0$, akkor az $I=(m)$ szerinti kongruencia ekvivalens a 18.3. Definícióban bevezetett $\bmod_m$ maradékképző függvény, mint gyűrűhomomorfizmus szerinti kongruenciával, hiszen az $I=(m)$ főideál épp ennek a gyűrűhomomorfizmusnak a magja. Mármost ennek a kongruenciának a maradékosztályai – amelyek tehát megegyeznek az $I=(m)$ főideál szerinti és így a modulo $m$ maradékosztályokkal – a 18.9. Definíció alapján épp azok a halmazok lesznek $\Z$-ben, amelyeknek az elemeihez a $\bmod_m$ maradékképző függvény azonos elemet rendel hozzá a 18.3. Definíció szerinti $Z_m$ halmazból. Ez látható a 20.1. ábrán.

Következésképp $m\gt 0$ esetben a modulo $m$ maradékosztályok száma épp meg fog egyezni a $Z_m$ gyűrű elemszámával, amely valóban $m$.

∎