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
Der euklidische Algorithmus
Erinnerst du dich noch, dass der grösste gemeinsame Teiler (ggT) von zwei Ganzzahlen A und B die grösste ganze Zahl ist, durch welche sowohl A und B teilbar sind?
Der Euklidische Algorithmus ist eine Technik zum raschen Berechnen des ggT zweier Ganzzahlen.
Der Algorithmus
Der euklidische Algorithmus für das Ermitteln des ggT(A,B) ist wie folgt:
- Wenn A = 0 dann ist ggT(A,B)=B, da ggT(0,B)=B und wir sind schon fertig.
- Wenn B = 0 dann ist ggT(A,B)=A, da ggT(A,0)=A und wir sind schon fertig.
- Schreibe a als Rest einer Division (A = B⋅Q +R)
- Ermittle ggT(B,R) indem du den euklidschen Algorithmus verwendest ggT(A,B) = ggT(B,R)
Beispiel:
Ermittle den ggT von 270 und 192
- A=270, B=192
- A ≠0
- B ≠0
- Führe eine schriftliche Divison durch und du erhältst 270/192 = 1 mit einem Rest von 78. Wir können dies auch schreiben als : 270 = 192 * 1 + 78
- Ermittle den ggT(192,78), da ggT(270,192)=ggT(192,78)
A=192, B=78
- A ≠0
- B ≠0
- Führe eine schriftliche Divison durch und du erhältst 192/78 = 2 mit einem Rest von 36. Wir können dies auch schreiben als :
- 192 = 78 * 2 + 36
- Ermittle den ggT(78,36), da ggT(192,78)=ggT(178,36)
A=78, B=36
- A ≠0
- B ≠0
- Führe eine schriftliche Divison durch und du erhältst 78/36 = 2 mit einem Rest von 6. Wir können dies auch schreiben als :
- 78 = 36 * 2 + 6
- Ermittle den ggT(36,6), da ggT(78,36)=ggT(36,6)
A=36, B=6
- A ≠0
- B ≠0
- Führe eine schriftliche Divison durch und du erhältst 36/6 = 6 mit einem Rest von 0. Wir können dies auch schreiben als :
- 36 = 6 * 6 + 0
- Ermittle den ggT(6,0), da ggT(36,6)=ggT(6,0)
A=6, B=0
- A ≠0
- B =0, ggT(6,0)=6
Also haben wir gezeigt:
ggT(270,192) = ggT(192,78) = ggT(78,36) = ggT(36,6) = ggT(6,0) = 6
ggT(270 192) = 6
Den euklidschen Algorithmus verstehen
Wenn wir den euklidschen Algorithmus untersuchen, können wir sehen, dass er folgenden Eigenschaften verwendet:
- ggT(A,0) = A
- ggT(0,B) = B
- Wenn A = B⋅Q + R und B≠0 dann ist ggT(A,B) = ggT(B,R) wenn Q eine Ganzzahl ist, R eine Ganzzahl zwischen 0 und B-1 ist
Mit den ersten beiden Eigenschaften können wir den ggT ermitteln wenn eine der beiden Zahlen 0 ist. Mit der dritten Eigenschaft können wir ein grösseres, schwieriger zu lösendes Problem auf ein kleineres, einfacher zu lösendes Problem reduzieren.
Der euklidische Algorithmus verwendet diese Eigenschaften indem er, durch verwenden der dritten Eigenschaft, das Problem schnell in leichter und leichtere Probleme reduziert, bis es schlussendlich leicht mit einer der ersten beiden Eigenschaften gelöst werden kann.
Wir können verstehen wie diese Eigenschaften funktionieren indem wir diese Beweisen.
ggt(A,0)=A kann folgendermaßen bewiesen werden:
- Die größte ganze Zahl, welche A ohne Rest dividiert ist A.
- 0 ist durch jede ganze Zahl ohne Rest teilbar, da für jede ganze Zahl C gilt: C ⋅ 0 = 0. Daher wissen wir, dass 0 durch A ohne Rest teilbar ist.
- Die grösste Zahl durch welche sowohl A als auch 0 teilbar sind ist A.
Der Beweis für GCD(0,B)=B ist ähnlich. (Gleicher Beweis, aber wir ersetzen A durch B).
Um zu Beweisen, dass GCD(A,B)=GCD(B,R) ist, müssen wir zuerst GCD(A,B)=GCD(B,A-B) beweisen.
Angenommen wir haben drei ganze Zahlen A,B und C und A-B=C.
Beweis, dass der C ohne Rest durch den ggT(A,B) teilbar ist
A ist per Definition durch den ggT(A,B) ohne Rest teilbar. Daher muss A ein Vielfaches vom ggt(A,B) sein. Das heißt X⋅ggT(A,B)=A, wobei X eine ganze Zahl ist.
B ist per Definition durch den ggT(A,B) ohne Rest teilbar. Daher muss B ein Vielfaches vom ggt(A,B) sein. Das heißt X⋅ggT(A,B)=B, wobei X eine ganze Zahl ist.
A-B=C gibt:
- X⋅GCD(A,B) - Y⋅GCD(A,B) = C
- (X - Y)⋅GCD(A,B) = C
Wir sehen daher, dass C durch den ggT(A,B) ohne Rest teilbar ist.
In der Abbildung unten ist der Beweis auch grafisch dargestellt:
Beweis, dass A ohne Rest durch den ggT(B,C) teilbar ist
B ist per Definition durch den ggT(B,C) ohne Rest teilbar. Daher muss B ein Vielfaches vom ggt(B,C) sein. Das heißt M⋅ggT(B,C)=B, wobei M eine ganze Zahl ist.
C ist per Definition durch den ggT(B,C) ohne Rest teilbar. Daher muss C ein Vielfaches vom ggt(B,C) sein. Das heißt N⋅ggT(B,C)=C, wobei N eine ganze Zahl ist.
A-B=C gibt:
- B+C=A
- M⋅ggT(B,C) + N⋅ggT(B,C) = A
- (M + N)⋅ggT(B,C) = A
Wir sehen daher, dass A durch den ggT(B,C) ohne Rest teilbar ist.
In der Abbildung unten ist der Beweis auch grafisch dargestellt:
Beweis, dass ggT(A,B)=ggT(A,A-B)
- B ist per Definition durch den ggT(A,B) ohne Rest teilbar.
- Wir haben bewiesen, dass C durch den ggT(A,B) ohne Rest teilbar ist.
- Da sowohl B als auch C durch den ggT(A,B) ohne Rest teilbar sind, ist dies ein gemeinsamer Teiler von B und C.
Der ggT(A,B) muss kleiner oder gleich dem ggT(B,C) sein, da der ggT(B,C) der “grösste” gemeinsame Teiler von B und C ist.
- B ist per Definition durch den ggT(B,C) ohne Rest teilbar.
- Wir haben bewiesen, dass A durch den ggT(B,C) ohne Rest teilbar ist.
- Da sowohl A als auch B durch den ggT(B,C) ohne Rest teilbar sind, ist dies ein gemeinsamer Teiler von A und B.
Der ggT(B,C) muss kleiner oder gleich dem ggT(A,B) sein, da der ggT(A,B) der “grösste” gemeinsame Teiler von A und B ist.
Da ggT(A,B)≤ggT(B,C) und ggT(B,C)≤ggT(A,B) schließen wir, dass:
ggT(A,B)=ggT(B,C)
Was das gleiche ist wie:
ggT(A,B)=ggT(B,A-B)
In der Abbildung unten auf der rechten Seite ist der Beweis auch grafisch dargestellt:
Beweis, dass ggT(A,B)=ggT(B,R)
Wir haben bewiesen, dass ggT(A,B)=ggT(B,A-B)
Die Reihenfolge der Terme spielt keine Rolle, daher können wir auch sagen : ggT(A,B)=ggT(A-B,B)
Wir können ggT(A,B)=ggT(A-B,B) wiederholt anwenden und erhalten:
ggT(A,B)=ggT(A-B,B)=ggT(A-2B,B)=ggT(A-3B,B)=...=ggT(A-Q⋅B,B)
Da aber A= B⋅Q + R ist A-Q⋅B=R
Und daher ist ggT(A,B)=ggT(R,B)
Die Reihenfolge der Terme spielt keine Rolle, daher ist:
ggT(A,B)=ggT(B,R)
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.