Bizonyítás
Tegyük fel indirekt, hogy nem ez a helyzet, vagyis annak ellenére, hogy [a]_n és [b]_n különböznek egymástól, mégiscsak teljesül az alábbi egyenlőség:
[c]_n \odot [a]_n = [c]_n \odot [b]_n
A \odot művelet 20.5. Tételben ismertetett definíciója alapján ez az alábbit jelenti:
[ca]_n = [cb]_n
A 20.4. Tétel alapján ugyanezt a kongruenciák nyelvén is kifejezhetjük:
ca\equiv cb\pmod n
Mivel [c]_n egy redukált maradékosztály, ezért a 20.15. Tétel alapján c relatív prím n-hez, és így a fenti kongruencia a 20.3. Tétel utáni megjegyzés szerint minden további nélkül egyszerűsíthető c-vel. Ezt kapjuk tehát:
a\equiv b\pmod n
Ez viszont azt jelenti, hogy indirekt feltételezésünkkel ellentétben a és b mégiscsak ugyanazt a maradékosztályt reprezentálja, ami ellentmondás.
∎