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

Vorgehensweise

Wenn man zwei Zahlen %%a%% und %%b%% gegeben hat, dann bestimmt man den größten gemeinsamen Teiler %%\text{ggT}(a,b)%% von %%a%% und %%b%% 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 %%a%% größer als %%b%% ist:

$$a=q_1\cdot b+r_0$$

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

$$b=q_2\cdot r_0+r_1$$

%%q_2%% und %%r_1%% sind dabei Zahlen, die aus der Rechnung (mit Rest) %%b:r_0=q_2 \text{ Rest }r_1%% hervorkommen. %%r_1%% ist also der Rest der Division der Zahlen %%b%% und %%r_0%%.

$$r_0=q_3\cdot r_1+r_2$$

%%q_3%% und %%r_2%% sind dabei Zahlen, die aus der Rechnung (mit Rest) %%r_0:r_1=q_3 \text{ Rest } r_2%% hervorkommen. %%r_2%% ist also der Rest der Division der Zahlen  %%r_0%% und %%r_1%%.

Man kann hier ein Schema erkennen:Geogebra File: https://assets.serlo.org/legacy/6716_szb0LAlyDI.xml

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

%%r_{n-2}=q_{n+1}\cdot r_{n-1}+0%%

Die Zahl %%r_{n-1}%% ist dann der %%\text{ggT}%% von %%a%% und %%b%%.

Erklärung am Beispiel

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

$$1071=q_1\cdot1029+r_0$$ $$\Rightarrow1071=1\cdot1029+42$$

Die Zahlen %%q_1%% und %%r_0%% errechnet man mit schriftlicher Division mit Rest:

$$\begin{array}{l}\begin{array}{ccc}1071:&1029&=1\;Rest\;42\\\underline{1029}&&\\\;\;\;42&&\end{array}\\\end{array}$$ damit ist %%q_1=1%% und %%r_0=42%%

$$1029=q_2\cdot42+r_1$$ $$\Rightarrow1029=24\cdot42+21$$

Die Zahlen %%q_2%% und %%r_1%% errechnet man so:

$$\begin{array}{l}\begin{array}{ccc}1029:&42&=24\;Rest\;21\\\;\underline{84\;}\;&&\\\;189&&\\\underline{\;168}&&\\\;\;\;21&&\end{array}\\\end{array}$$ damit ist %%q_2=24%% und %%r_1=21%%

$$42=q_3\cdot21+r_2$$ $$\Rightarrow42=2\cdot21+0$$

Die Zahlen %%q_3%% und %%r_2%% errechnet man so:

$$\begin{array}{l}\begin{array}{ccc}42:&21&=2\;Rest\;0\\\;\underline{42\;}\;&&\\\;\;0&&\end{array}\\\end{array}$$ damit ist %%q_3=2%% und %%r_2=0%%

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

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

Kommentieren Kommentare

Zu article Euklidischer Algorithmus: Vorschläge für Änderungen
peterjaumann 2015-12-01 10:40:54+0100
Die beiden allgemeinen Erklärungen des Algorithmus sollten durch eine Überschrift voneinander getrennt werden. Außerdem ist das Layout unter "Erklärungen am Beispiel" etwas irreführend. Eventuell besser mit 1:2-Unterteilung?
Antwort abschicken