Hauptinhalt

Modulare Kehrzahlen

Was ist der Kehrwert?

Erinnere dich daran, dass eine Zahl multipliziert mit ihrem Kehrwert gleich 1 ist. Aus den Grundlagen der Arithmetik wissen wir:

Der Kehrwert einer Zahl A ist 1/A, da A * 1/A = 1 ist (z. B. ist der Kehrwert von 5 1/5).
Alle reellen Zahlen außer 0 haben einen Kehrwert
Die Multiplikation einer Zahl mit dem Kehrwert von A ist äquivalent zur Division durch A (z. B. ist 10/5 dasselbe wie 10* 1/5)

Was ist der modulare Kehrwert?

Im modularen Rechnen wir haben keine Divisionsoperation. Aber wir haben den modulare Kehrwert.

Der modulare Kehrwert von A (mod C) ist A^-1
(A * A^-1) ≡ 1 (mod C) oder gleichwertig (A * A^-1) mod C = 1
Nur die Zahlen, die teilerfremd zu C sind (Zahlen, die keine gemeinsamen Primfaktoren mit C haben) haben einen modularen Kehrwert (mod C)

So findest du eine modulare Kehrzahl

Eine einfache Methode eine modulare Kehrzahl für zu finden, (mod C) ist:

Schritt 1. Berechne A * B mod C für B-Werte von 0 bis C-1

Schritt 2. Die modulare Kehrzahl von A mod C ist der B Wert aus A * B mod C = 1

Beachte dass der Term B mod C nur einen ganzzahligen Wert 0 bis C-1 haben kann, also ist das testen für größere Werte von B redundant.

Beispiel: A=3, C=7

Schritt 1. Berechne A * B mod C für Werte von B von 0 bis C-1

3 * 0 ≡ 0 (mod 7)

3 * 1 ≡ 3 (mod 7)

3 * 2 ≡ 6 (mod 7)

3 * 3 ≡ 9 ≡ 2 (mod 7)

3 * 4 ≡ 12 ≡ 5 (mod 7)

3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ KEHRZAHL GEFUNDEN!

3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

**Schritt 2. Die modulare Kehrzahl von A mod C ist der Wert von B aus A * B mod C = 1**

5 ist die modulare Kehrzahl von 3 mod 7 da 5*3 mod 7 = 1

Einfach!

Lass uns noch ein weiteres Beispiel rechnen, wo wir keine Inverse finden werden.

Beispiel: A=2 C=6

**Schritt 1. Berechne A * B mod C für B-Werte von 0 bis C-1**

2 * 0 ≡ 0 (mod 6)

2 * 1 ≡ 2 (mod 6)

2 * 2 ≡ 4 (mod 6)

2 * 3 ≡ 6 ≡ 0 (mod 6)

2 * 4 ≡ 8 ≡ 2 (mod 6)

2 * 5 ≡ 10 ≡ 4 (mod 6)

**Schritt 2. Die modulare Kehrzahl von A mod C ist der Wert B aus A * B mod C = 1**

Es gibt keinen Wert B dass A * B mod C = 1. Daher hat A keine Modulare Kehrzahl (mod 6).
Dies daher, da 2 nicht teilerfremd zu 6 ist (sie haben den gemeinsamen Teiler 2).

Diese Methode scheint langsam...

Es gibt eine viel schnellere Methode für die Inverse von A(mod C), die wir in den folgenden Artikeln über den erweiterten euklidischen Algorithmus diskutieren werden.

Willst du an der Diskussion teilnehmen?

Anmelden

Sortiere nach:

Noch keine Beiträge.

Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Informationstechnik

Kurs: Informationstechnik > Lerneinheit 2