Nach der Definition der Kongruenz zweier Zahlen modulo ´m´ gilt:

´a -= b \ ("mod m") <=>´ ´m | (a-b) <=>´ ´(a-b) in mZZ´

Nun soll gezeigt werden: ´r_1 = r_2 => m | (a - b) => a -= b \ ("mod m")´

Es fehlt: ´a -= b \ ("mod m") => m | (a - b)´

Es sei ´a = q_1m + r_1´ und ´b = q_2m + r_2´ mit ´0 <= r_1, r_2 <= m´.

´a - b = q_1m + r_1 - q_2m + r_2´ ´= m(q_1 - q_2) + r_1 - r_2´

Für ´r_1 = r_2´: ´a - b = m(q_1 - q_2)´

´=> m | (a - b)´ ´=> a -= b \ ("mod m")´

Durch die Umkehrbarkeit der Operationen gilt auch: ´a -= b \ ("mod m") => m | (a - b) => r_1 = r_2´

Somit ist ´a -= b \ ("mod m")´ gleichbedeutend mit "´a´ und ´b´ lassen bei der Division durch ´m´ denselben Rest".

Damit modulo ´m´ eine Äquivalenzrelation ist müssen nun folgende Eigenschaften gelten:

• reflexiv: ´a -= a \ ("mod m")´
• transitiv: ´a -= b \ ("mod m") ^^ b -= c \ ("mod m") => a -= c \ ("mod m")´
• symmetrisch: ´a -= b \ ("mod m") => b -= a \ ("mod m")´

Dies lässt sich nun mit den vorhergegangenen Umformungen leicht zeigen:

• reflexiv: Es gilt ´m | (a - a)´, da jede Zahl die Null teilt
• transitiv: Aus ´m | (a − b)´ folgt ´m | −(a − b)´ bzw. ´m | (b − a)´
• symmetrisch: Aus ´m | (a − b)´ und ´m | (b − c)´ folgt ´m | (a − b) + (b − c)´ bzw. ´m | (a − c)´