Der Euklidische Algorithmus für große Zahlen - Berechnungsmethode des größten gemeinsamen Teilers, ggT, und des kleinsten gemeinsamen Vielfachen, kgV; kgV (a; b) = (a × b) / ggT (a; b) - die Theorie, Beispiele und Erklärungen
Finden Sie die größten gemeinsamen Teiler (ggT) für große Zahlen
Bei großen Zahlen ist die Primfaktorzerlegung schwierig. Wenn wir für so große Zahlen den größten gemeinsamen Teiler (ggT) berechnen müssen, wäre eine Methode ohne Primfaktorzerlegung praktisch. Der euklidische Algorithmus ist eine solche Methode zur Berechnung des ggT, siehe die Beispiele unten.
Dieser Algorithmus beginnt mit dem Teilen der Zahlen und dem Aufzeichnen der Reste jeder dieser Operationen.
Wenn 'a' und 'b' die beiden positiven ganzen Zahlen sind, 'a' >= 'b'.
Teilen Sie 'a' durch 'b' und erhalten Sie den Rest, 'r'.
Wenn 'r' = 0 ist, STOP. 'b' ist der ggT von 'a' und 'b'.
Sonst: Ersetzen Sie ('a' durch 'b') und ('b' durch 'r'). Kehren Sie zum obigen Schritt der Teilung zurück.
Mal sehen, was der größte gemeinsame Teiler (ggT) der Zahlen 53.667 und 25.527 ist:
[1] Ich beginne damit, die größere Zahl durch die kleinere zu dividieren:
53.667 : 25.527 = 2 und der Rest = 2.613 => 53.667 = 25.527 × 2 + 2.613
[2] Ich dividiere dann die kleinere Zahl durch den Rest der obigen Operation:
25.527 : 2.613 = 9 und der Rest = 2.010 => 25.527 = 2.613 × 9 + 2.010
[3] Ich dividiere den Rest der ersten Operation durch den Rest der zweiten Operation:
2.613 : 2.010 = 1 und der Rest = 603 => 2.613 = 2.010 × 1 + 603
[4] Ich dividiere den Rest der zweiten Operation durch den Rest der dritten Operation:
2.010 : 603 = 3 und der Rest = 201 => 2.010 = 603 × 3 + 201
[5] Ich dividiere den Rest der dritten Operation durch den Rest der vierten Operation:
603 : 201 = 3 und der Rest = 0 => 603 = 201 × 3
Bei diesem Schritt ist der Rest Null, also müssen wir aufhören: 201 ist die Zahl, nach der wir gesucht haben.
Abschließend:
201 ist der letzte Rest, der von Null verschieden war. Dies ist der größte gemeinsame Teiler der Zahlen.
Der größte gemeinsame Teiler der beiden Zahlen ist also der letzte Rest, der von Null verschieden ist.
Wenn dieser letzte Rest gleich eins ist, dann sind die beiden Zahlen zueinander teilerfremd.
Für die obigen Operationen ist der letzte Rest ungleich Null, 201, der größte gemeinsame Teiler (ggT) der Zahlen 53.667 und 25.527.
Mit Hilfe des Euklidischen Algorithmus können wir beweisen, dass zwei Zahlen relativ teilerfremd sind, siehe Beispiel unten.
Berechnen Sie den ggT (87, 41):
[1] Ich beginne damit, die größere Zahl durch die kleinere zu dividieren:
87 : 41 = 2 und der Rest = 5 => 87 = 41 × 2 + 5
[2] Ich dividiere dann die kleinere Zahl durch den Rest der obigen Operation:
41 : 5 = 8 und der Rest = 1 => 41 = 5 × 8 + 1
[3] Ich dividiere den Rest der ersten Operation durch den Rest der zweiten Operation:
5 : 1 = 5 und der Rest = 0 => 5 = 1 × 5 + 0
Der letzte Nicht-Null-Rest aus den obigen Operationen ist gleich 1.
ggT (87, 41) = 1, also sind die Zahlen teilerfremd.
Warum ist die Antwort also ein Teiler der Anfangswerte 'a' und 'b'?
Hinweis: Die Division 'a' : 'b' = 'q' + 'r' entspricht der Gleichung: 'a' = 'b' × 'q' + 'r', wobei 'q' der Quotient der Division ist.
Wenn der Endwert von 'r' = 0 ist, dann ist der Endwert von 'b' ein Teiler des Endwerts von 'a', da 'a' = 'b' × 'q' + 0.
Wenn 'rn' = 0 => Gemäß dem n. Schritt: 'r(n-1)' ist ein Teiler von 'r(n-2)'.
'r(n-1)' ist auch der letzte Rest ungleich Null.
Gemäß dem (n-1). Schritt: 'r(n-1)' ist ein Teiler von sowohl 'r(n-1)' (selbst) als auch 'r(n-2)', also ist es auch ein Teiler von 'r(n-3)'.
Gemäß dem (n-2). Schritt: 'r(n-1)' ist ein Teiler von sowohl 'r(n-2)' als auch 'r(n-3)', also ist es auch ein Teiler von 'r(n-4)'.
Gemäß dem (n-3). Schritt: 'r(n-1)' ist ein Teiler von sowohl 'r(n-3)' als auch 'r(n-4)', also ist es auch ein Teiler von 'r(n-5)'.
...
Gemäß dem 3. Schritt: 'r(n-1)' ist ein Teiler von sowohl 'r3' als auch 'r2', also ist es auch ein Teiler von 'r1'.
Gemäß dem 2. Schritt: 'r(n-1)' ist ein Teiler von sowohl 'r2' als auch 'r1', also ist es auch ein Teiler von 'b'.
Gemäß dem 1. Schritt: 'r(n-1)' ist ein Teiler von sowohl 'r1' als auch 'b', also ist es auch ein Teiler von 'a'.
Der letzte Rest ungleich Null, r(n-1), ist also ein Teiler sowohl von 'a' als auch von 'b'.
Warum ist die Antwort immer gleich dem größten gemeinsamen Teiler?
Wie wir oben gesehen haben, ist der letzte Nicht-Null-Rest ein Teiler von 'a' und 'b'. Nennen wir diesen Teiler 't'.
Gemäß dem 1. Divisionsschritt: Wenn 't' sowohl ein Teiler von 'a' als auch von 'b' ist, dann ist es auch ein Teiler von 'r1'.
Gemäß dem 2. Divisionsschritt: Wenn 't' sowohl ein Teiler von 'b' als auch von 'r1' ist, dann ist es auch ein Teiler von 'r2'.
Und so weiter bis zum (n-1). Schritt: Wenn 't' ein Teiler von 'r(n-3)' und 'r(n-2)' ist, dann ist es auch ein Teiler von 'r(n-1)'. Aber wie wir oben berechnet haben, ist dieser Divisor der letzte Nicht-Null-Rest, der in unserem Fall 'r(n-1)' ist.
Also konnte 't' nicht größer als 'r(n-1)' sein, da es ein Teiler davon sein muss.
Anwendung des Euklidischen Algorithmus für mehr als zwei Zahlen:
Der euklidische Algorithmus kann auch verwendet werden, um die größten gemeinsamen Teiler mehrerer Zahlen wie 'a', 'b' und 'c' zu finden.
Zuerst berechnen wir ggT ('a', 'b') = 'd' und danach berechnen wir ggT ('c', 'd').
Der Euklidische Algorithmus: Berechnen Sie das kleinste gemeinsame Vielfache (kgV) für große Zahlen
Bei großen Zahlen wird es unpraktisch, das kleinste gemeinsame Vielfache (kgV) zu berechnen, weil die Primfaktorzerlegung zu lange dauert.
Mit Hilfe des euklidischen Algorithmus wird nicht nur der größte gemeinsame Teiler (ggT) gefunden – wie oben gesehen, sondern auch das kleinste gemeinsame Vielfache (kgV) berechnet, nach der Formel:
kgV ('a', 'b') = ('a' × 'b') / ggT ('a', 'b')
Diese Methode kann verwendet werden, wenn nicht mehr als zwei Zahlen vorhanden sind.
Beweis der kgV-Formel
Angenommen, die Primzerlegungen von 'a' und 'b' sind: