Euklidischer Algorithmus

Der Euklidische Algorithmus ist sehr hilfreich zur Bestimmung des größten gemeinsamen Teilers (ggT) .

Vorgehensweise

Wenn man zwei Zahlen aa und bb gegeben hat, dann bestimmt man den größten gemeinsamen Teiler ggT(a,b)\text{ggT}(a,b) von aa und bb folgendermaßen:

  1. Teile (mit Rest) die größere der beiden Zahlen durch die kleinere.

  2. Teile nun die kleinere der beiden Zahlen durch den Rest der bei Schritt 1 herauskommt.

  3. Teile nun den Rest der bei Schritt 1 herauskommt durch den Rest der bei Schritt 2 herauskommt.

  4. Teile nun den Rest der bei Schritt 2 herauskommt durch den Rest der bei Schritt 3 herauskommt.

  5. Führe dies sooft durch bis bei einer Rechnung der Rest 0 herauskommt.

  6. Der Divisor bei dieser Rechnung ist der ggT der Zahlen a und b.

Allgemeine mathematische Schreibweise

Das ganze noch in einer allgemeinen mathematischen Schreibweise:

Man nehme an, dass aa größer als bb ist:

q1q_1 und r0r_0 sind dabei Zahlen, die aus der Rechnung (mit Rest) a:b=q1 Rest r0a:b=q_1 \text{ Rest } r_0 hervorkommen. r0r_0 ist also der Rest der Division der Zahlen von aa und bb.

q2q_2 und r1r_1 sind dabei Zahlen, die aus der Rechnung (mit Rest) b:r0=q2 Rest r1b:r_0=q_2 \text{ Rest }r_1 hervorkommen. r1r_1 ist also der Rest der Division der Zahlen bb und r0r_0.

q3q_3 und r2r_2 sind dabei Zahlen, die aus der Rechnung (mit Rest) r0:r1=q3 Rest r2r_0:r_1=q_3 \text{ Rest } r_2 hervorkommen. r2r_2 ist also der Rest der Division der Zahlen  r0r_0 und r1r_1.

Man kann hier ein Schema erkennen:

Führe dies sooft durch bis bei einer Rechnung Rest 0 herauskommt:

Die Zahl rn1r_{n-1} ist dann der ggT\text{ggT} von aa und bb.

Erklärung am Beispiel

Man hat die zwei Zahlen a=1071a=1071 und b=1029b=1029.

Die Zahlen q1q_1 und r0r_0 errechnet man mit schriftlicher Division mit Rest:

damit ist q1=1q_1=1 und r0=42r_0=42

Die Zahlen q2q_2 und r1r_1 errechnet man so:

damit ist q2=24q_2=24 und r1=21r_1=21

Die Zahlen q3q_3 und r2r_2 errechnet man so:

damit ist q3=2q_3=2 und r2=0r_2=0

Also ist  r1=21r_1=21 der größte gemeinsame Teiler von 1071 und 1029: ggT(1071,1029)=21\text{ggT}(1071{,}1029)=21


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0.Was bedeutet das?