Az [a]_m maradékosztály a 20.6. Definíció alapján pontosan akkor redukált, ha invertálható, azaz egyértelműen létezik olyan X=[x]_m maradékosztály, amelyre teljesül az alábbi:

[a]_m\odot X=[a]_m\odot [x]_m=[a\cdot x]_m=[1]_m

Ez pontosan az alábbi lineáris kongruencia egyértelmű megoldhatóságát jelenti:

ax\equiv 1\pmod m

Ez viszont a 20.12. Tétel szerint pontosan 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, vagy más szavakkal a relatív prím az m modulushoz (lásd a 17.10. Definíció utáni megjegyzést).

Válasszuk a pozitív egységet kitüntetett közös osztónak, azaz legyen (a,m)=1. Ebben az esetben a megoldások száma a 20.13. Tétel értelmében (a,m)=1. Vagyis a megoldás valóban egyértelmű.

Most igazoljuk a tétel másik állítását, miszerint egy maradékosztály minden 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:

b=k_1m+a

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. pontjai 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:

a=k_2m+b

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, ezért a 16.9. Tétel miatt (a,m) és (b,m) valóban asszociáltak.

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.