Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Euklidischer Algorithmus

Bild

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

VorgehenAlgorithmus

Wenn man zwei natürliche 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 11 herauskommt.

  3. Teile nun den Rest der bei Schritt 11 herauskommt durch den Rest der bei Schritt 22 herauskommt.

  4. Teile nun den Rest der bei Schritt 22 herauskommt durch den Rest der bei Schritt 33 herauskommt.

  5. Führe dies so oft durch, bis bei einer Rechnung der Rest 00 herauskommt.

  6. Der Divisor bei dieser Rechnung ist der ggT der Zahlen aa und bb.

Allgemeine mathematische Schreibweise

Das ganze noch in einer allgemeinen mathematischen Schreibweise:

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

Rechnung

Beschreibung

a=q1b+r0a=q_1\cdot b+r_0

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.

b=q2r0+r1b=q_2\cdot r_0+r_1

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.

r0=q3r1+r2r_0=q_3\cdot r_1+r_2

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.

Geogebra File: https://assets.serlo.org/legacy/6716_szb0LAlyDI.xml

Führe dies so oft durch, bis bei einer Rechnung Rest 00 herauskommt.

Man kann hier ein Schema erkennen:

Rechnung\phantom{Rechnung}

Beschreibung\phantom{Beschreibung}

rn2=qn+1rn1+0r_{n-2}=q_{n+1}\cdot r_{n-1}+0

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.

Rechnung

Beschreibung

1071=q11029+r01071=q_1\cdot1029+r_0 \\ 1071=11029+42\Rightarrow1071=1\cdot1029+42

Die Zahlen q1q_1 und r0r_0 errechnet man mit schriftlicher Division mit Rest: \\ 1071:1029=1  Rest  421029      42\def\arraystretch{1.25} \begin{array}{l}\begin{array}{ccc}1071:&1029&=1\;Rest\;42\\\underline{1029}&&\\\;\;\;42&&\end{array}\end{array} \\ damit ist q1=1q_1=1 und r0=42r_0=42

1029=q242+r11029=q_2\cdot42+r_1 \\ 1029=2442+21\Rightarrow1029=24\cdot42+21

Die Zahlen q2q_2 und r1r_1 errechnet man so: 1029:42=24  Rest  21  84      189  168      21\def\arraystretch{1.25} \begin{array}{l}\begin{array}{ccc}1029:&42&=24\;Rest\;21\\\;\underline{84\;}\;&&\\\;189&&\\\underline{\;168}&&\\\;\;\;21&&\end{array}\end{array} \\ damit ist q2=24q_2=24 und r1=21r_1=21

42=q321+r242=q_3\cdot21+r_2 \\ 42=221+0\Rightarrow42=2\cdot21+0

Die Zahlen q3q_3 und r2r_2 errechnet man so: \\ 42:21=2  Rest  0  42        0\def\arraystretch{1.25} \begin{array}{l}\begin{array}{ccc}42:&21&=2\;Rest\;0\\\;\underline{42\;}\;&&\\\;\;0&&\end{array}\end{array} \\ damit ist q3=2q_3=2 und r2=0r_2=0

Geogebra File: https://assets.serlo.org/legacy/6732_yAf2CCUneY.xml

Also ist  r1=21r_1=21 der größte gemeinsame Teiler von 10711071 und 10291029:

ggT(1071,1029)=21\text{ggT}(1071{,}1029)=21

Übungsaufgaben: Euklidischer Algorithmus

Du hast noch nicht genug vom Thema?

Hier findest du noch weitere passende Inhalte zum Thema:

Artikel


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