youproof.orgDeep Math. Human Access.

Bizonyítás

Tegyük fel indirekt, hogy nem ez a helyzet, vagyis annak ellenére, hogy [a]n[a]_n és [b]n[b]_n különböznek egymástól, mégiscsak teljesül az alábbi egyenlőség:

[c]n⊙[a]n=[c]n⊙[b]n[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[ca]_n = [cb]_n

A 20.4. Tétel alapján ugyanezt a kongruenciák nyelvén is kifejezhetjük:

ca≡cb(modn)ca\equiv cb\pmod n

Mivel [c]n[c]_n egy redukált maradékosztály, ezért a 20.15. Tétel alapján cc relatív prím nn-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ő cc-vel. Ezt kapjuk tehát:

a≡b(modn)a\equiv b\pmod n

Ez viszont azt jelenti, hogy indirekt feltételezésünkkel ellentétben aa és bb mégiscsak ugyanazt a maradékosztályt reprezentálja, ami ellentmondás.

∎