Bizonyítás
Az [a]_m maradékosztály a 20.6. Definíció alapján pontosan akkor redukált, ha invertálható, azaz létezik pontosan egy olyan X=[x]_m maradékosztály, amelyre teljesül az alábbi:
Ez pontosan az alábbi lineáris kongruencia egyértelmű megoldhatóságát jelenti:
Ez viszont a 20.13. Tétel szerint akkor és csak akkor oldható meg, ha teljesül az (a,m)|1 oszthatóság. Ez a 16.5. Tétel alapján azt jelenti, hogy az (a,m) kitüntetett közös osztó egység, ami a 17.10. Definíció utáni megjegyzés szerint épp azt jelenti, hogy a relatív prím az m modulushoz, azaz
Válasszuk a pozitív egységet kitüntetett közös osztónak, azaz legyen (a,m)=1. Ebben az esetben a lineáris kongruencia megoldásainak száma a 20.14. Tétel értelmében 1, azaz a megoldás egyértelmű.
Most igazoljuk a tétel másik állítását, miszerint bármely maradékosztály összes elemének asszociáltság erejéig ugyanaz az m modulussal vett kitüntetett közös osztója. Az [a]_m=[b]_m egyenlőség azt jelenti, hogy a ugyanabban a maradékosztályban van, mint b. Így tehát a 20.4. Tétel alapján a b egész szám felírható az alábbi alakban valamilyen alkalmas k_1 egész szám segítségével:
Mivel az (a,m) kitüntetett közös osztó osztója a-nak és m-nek, ezért a 16.2. Tétel 7. és 6. pontja miatt osztója k_1m+a=b-nek is. Így tehát (a,m) közös osztója b-nek és m-nek, vagyis a 17.4. Definíció alapján osztója ezek kitüntetett közös osztójának, azaz teljesül az (a,m)|(b,m) oszthatóság.
Ugyanígy a 20.4. Tétel alapján az a egész szám is felírható az alábbi alakban valamilyen alkalmas k_2 egész szám segítségével:
Ebből az előző gondolatmenetet megismételve azt fogjuk kapni, hogy teljesül a (b,m)|(a,m) oszthatóság. Minthogy mindkét irányban fennáll az oszthatóság (a,m) és (b,m) között, ezért a 16.9. Tétel miatt:
Speciálisan ha a relatív prím m-hez, akkor (a,m) egység, és így az asszociáltság miatt (b,m) is egység, azaz b is relatív prím m-hez.
∎