Der Euklidische Algorithmus für große Zahlen, Theorie

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.

[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.

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.

[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.

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.

Berechnen wir die ggT (a, b):
1. Schritt: 'a' = 'b' × 'q₁' + 'r₁', 'r₁' nicht null.
2. Schritt: 'b' = 'r₁' × 'q₂' + 'r₂', 'r₂' nicht null.
3. Schritt: 'r₁' = 'r₂' × 'q₃' + 'r₃', 'r₃' nicht null.
...
(n-3). Schritt: 'r_(n-5)' = 'r_(n-4)' × 'q_(n-3)' + 'r_(n-3)', 'r_(n-3)' nicht null.
(n-2). Schritt: 'r_(n-4)' = 'r_(n-3)' × 'q_(n-2)' + 'r_(n-2)', 'r_(n-2)' nicht null.
(n-1). Schritt: 'r_(n-3)' = 'r_(n-2)' × 'q_(n-1)' + 'r_(n-1)', 'r_(n-1)' nicht null.
n. Schritt: 'r_(n-2)' = 'r_(n-1)' × 'q_n' + 'r_n', 'r_n' = Null.
Der Rest ist Null, wir müssen aufhören.

Wenn 'r_n' = 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 'r₃' als auch 'r₂', also ist es auch ein Teiler von 'r₁'.
Gemäß dem 2. Schritt: 'r_(n-1)' ist ein Teiler von sowohl 'r₂' als auch 'r₁', also ist es auch ein Teiler von 'b'.
Gemäß dem 1. Schritt: 'r_(n-1)' ist ein Teiler von sowohl 'r₁' 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'.

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 'r₁'.
Gemäß dem 2. Divisionsschritt: Wenn 't' sowohl ein Teiler von 'b' als auch von 'r₁' ist, dann ist es auch ein Teiler von 'r₂'.
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.

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').

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.