Modulare Addition und Subtraktion

Gegeben A=14, B=17, C=5

Wir überprüfen: (A + B) mod C = (A mod C + B mod C) mod C
LHS = linke Seite der Gleichung
RHS = Rechte Seite der Gleichung

LHS = (A + B) mod C
LHS = (14 + 17) mod 5
LHS = 31 mod 5
LHS = 1

RHS = (A mod C + B mod C) mod C
RHS = (14 mod 5 + 17 mod 5) mod 5
RHS = (4 + 2) mod 5
RHS = 1

Betrachte die untenstehende Abbildung. Wenn wir 12 + 9 mod 7 berechnen möchten, können wir leicht um den modularen Kreis für eine Folge von 12 + 9 Schritten im Uhrzeigersinn (wie in der Kreis unten links darstellt) gehen.

Wir können den Prozess verkürzen, durch die Beobachtung, dass wir alle 7 Schritte auf der gleichen Position des modularen Kreises landen. Diese kompletten Schleifen um den modularen Kreis beeinflussen unsere endgültige Position nicht. Wir ignorieren diese kompletten Schleifen um den Kreis damit, dass wir jede Zahl mod 7 rechnen (wie in den beiden oberen modularen Kreisen dargestellt). Das gibt uns die Anzahl Schritte im Uhrzeigersinn, im Vergleich zu 0, geben, die zu ihrer jeweiligen Position auf dem modularen Kreis beigetragen haben.

Nun müssen wir nur noch beim Kreis im Uhrzeigersinn die insgesamt die Anzahl der Schritte gehen, die zu den Endpositionen aller Zahlen beitragen (ersichtlich im Kreis unten rechts). Diese Methode gilt im Allgemeinen für zwei ganze Zahlen - egal welche - und jeden modularen Kreis.

Wir werden beweisen, dass (A + B) mod C = (A mod C + B mod C) mod C
Wir müssen beweisen, dass LHS RHS =

Ausgehend vom Satz von der Division mit Rest können wir A und B schreiben als:

A = C * Q1 + R1 wobei 0 ≤ R1 < C und Q1 ist eine ganze Zahl. A mod C = R1
B = C * Q2 + R2 wobei 0 ≤ R2 < C und Q2 ist eine ganze Zahl. B mod C R2 =
(A + B) = C * (Q1 + Q2) + R1 + R2

LHS = (A + B) mod C
LHS = (C * (Q1 + Q2) + R1 + R2) mod C
Wir können die Vielfache von C beseitigen, wenn wir die mod C
LHS = (R1 + R2) mod C

RHS = (A mod C + B mod C) mod C
RHS = (R1 + R2) mod C

Ein sehr ähnlicher Beweis gilt für die modulare Subtraktion