Euklidischer Algorithmus

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

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

Teile (mit Rest) die größere der beiden Zahlen durch die kleinere.
Teile nun die kleinere der beiden Zahlen durch den Rest, der bei Schritt $1$ herauskommt.
Teile nun den Rest der bei Schritt $1$ herauskommt durch den Rest der bei Schritt $2$ herauskommt.
Teile nun den Rest der bei Schritt $2$ herauskommt durch den Rest der bei Schritt $3$ herauskommt.
Führe dies so oft durch, bis bei einer Rechnung der Rest $0$ herauskommt.
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:

Rechnung	Beschreibung
$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$ .

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

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

Man kann hier ein Schema erkennen:

$\phantom{Rechnung}$	$\phantom{Beschreibung}$
$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$ .

Rechnung	Beschreibung
$1071=q_1\cdot1029+r_0$ $\\$ $\Rightarrow1071=1\cdot1029+42$	Die Zahlen $q_1$ und $r_0$ errechnet man mit schriftlicher Division mit Rest: $\\$ $\def\arraystretch{1.25} \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: $\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 $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: $\\$ $\def\arraystretch{1.25} \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$

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

Also ist $r_1=21$ der größte gemeinsame Teiler von $1071$ und $1029$ :

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

Übungsaufgaben: Euklidischer Algorithmus

Laden

Du hast noch nicht genug vom Thema?

Hier findest du noch weitere passende Inhalte zum Thema:

Artikel

Teilermenge

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