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


$r_{n - 2} = q_{n + 1} \cdot r_{n - 1} + 0$	Die Zahl $r_{n - 1}$ ist dann der $ggT$ von $a$ und $b$ .

Erklärung am Beispiel

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

Rechnung	Beschreibung
$1071 = q_{1} \cdot 1029 + r_{0}$ $\Rightarrow 1071 = 1 \cdot 1029 + 42$	Die Zahlen $q_{1}$ und $r_{0}$ errechnet man mit schriftlicher Division mit Rest: $\begin{array}{l} \begin{array}{ccc} 1071 : & 1029 & = 1 R e s t 42 \\ 1029 \\ 42 \end{array} \end{array}$ damit ist $q_{1} = 1$ und $r_{0} = 42$
$1029 = q_{2} \cdot 42 + r_{1}$ $\Rightarrow 1029 = 24 \cdot 42 + 21$	Die Zahlen $q_{2}$ und $r_{1}$ errechnet man so: $\begin{array}{l} \begin{array}{ccc} 1029 : & 42 & = 24 R e s t 21 \\ 84 \\ 189 \\ 168 \\ 21 \end{array} \end{array}$ damit ist $q_{2} = 24$ und $r_{1} = 21$
$42 = q_{3} \cdot 21 + r_{2}$ $\Rightarrow 42 = 2 \cdot 21 + 0$	Die Zahlen $q_{3}$ und $r_{2}$ errechnet man so: $\begin{array}{l} \begin{array}{ccc} 42 : & 21 & = 2 R e s t 0 \\ 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$ :

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