Hauptinhalt

Modulare Multiplikation

Lass' uns die Multiplikationseigenschaften der Zahlentheorie erkunden:

(A * B) mod C = (A mod C * B mod C) mod C

Es sei A=4, B=7, C=6

Lass' uns ü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 = (4 * 7) mod 6

LHS = 28 mod 6

LHS = 4

RHS = (A mod C * B mod C) mod C

RHS = (4 mod 6 * 7 mod 6) mod 6

RHS = (4 * 1) mod 6

RHS = 4 mod 6

RHS = 4

LHS = RHS = 4

Wir werden beweisen, dass (A * B) mod C = (A mod C * B mod C) mod C

Wir müssen zeigen, dass LHS = RHS

Wegen dem 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

LHS = (A * B) mod C

LHS = ((C * Q1 + R1) * (C * Q2 + R2)) mod C

LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

Wir können die Vielfachen von C eliminieren, indem wir den mod von C nehmen

LHS = (R1 * R2) mod C

Als nächstes machen wir RHS

RHS =(A mod C * B mod C) mod C

RHS = (R1 * R2 ) mod C

Daher ist RHS = LHS

LHS = RHS = (R1 * R2 ) mod C

Sortiere nach:

Noch keine Beiträge.