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}$ .

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

Man kann hier ein Schema erkennen:

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

$\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$

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

Übungsaufgaben

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?