Euklidischer Algorithmus

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

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

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

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

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