Hauptinhalt
Informationstechnik
Kurs: Informationstechnik > Lerneinheit 2
Lesson 5: Modulare Arithmetik- Was ist modulare Arithmetik?
- Modulo-Operator
- Modulo-Challenge
- Kongruenz Modul
- Kongruenzrelation
- Gleichwertigkeitsbeziehungen
- Das Quotientenrest-Theorem
- Modulare Addition und Subtraktion
- Modulare Addition
- Herausforderung zum Modulusoperator (Addition und Subtraktion)
- Modulare Multiplikation
- Modulare Multiplikation
- Modulare Exponentialrechnung
- Schnelle modulare Exponentialrechnung
- Schnelle modulare Exponentialrechnung
- Modulare Kehrzahlen
- Der euklidische Algorithmus
© 2023 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung
Modulare Addition und Subtraktion
Entdecke die Additions-Eigenschaften der modularen Arithmetik:
(A + B) mod C = (A mod C + B mod C) mod C
Beispiel:
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 = 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
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
RHS = (14 mod 5 + 17 mod 5) mod 5
RHS = (4 + 2) mod 5
RHS = 1
LHS = RHS = 1
Idee hinter modularer Addition
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.
Beweis für die modulare Addition
Wir werden beweisen, dass (A + B) mod C = (A mod C + B mod C) mod C
Wir müssen beweisen, dass LHS RHS =
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
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
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
RHS = (R1 + R2) mod C
LHS = RHS = (R1 + R2) mod C
Modulare Subtraktion
Ein sehr ähnlicher Beweis gilt für die modulare Subtraktion
(A - B) mod C = (A mod C - B mod C) mod C
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.