Der Euklidische Algorithmus
Als erstes Beispiels sei gefragt, wie der größte gemeinsame Teiler (kurz: $\mathrm{ggT}$) zweier ganzen Zahlen am effektivsten berechnet werden kann. Ein bewährtes Verfahren dafür ist der Euklidische Algorithmus, welcher nach dem griechischen Mathematiker Euklid benannt wurde.
Der Algorithmus wird zunächst formal und allgemein beschrieben und anschließend mit einem Zahlenbeispiel veranschaulicht.
Das Verfahren
Seien $a,b \in \mathbb{Z}$. Angenommen, $b$ ist kein Teiler von $a$ (da sonst $\mathrm{ggT}(a,b) = b$). Zudem sei ohne Beschränkung der Allgemeinheit $a$ die größere der beiden Zahlen.
Die Idee, die dem Algorithmus zugrunde liegt, ist, dass jede Zahl, die $a$ und $b$ teilt, auch die Linearkombination $a + \mu b$ teilt für alle $\mu\in\mathbb{Z}$. Darüber hinaus gilt sogar, dass $\mathrm{ggT}(a,b) = \mathrm{ggT}(a + \mu b,b)$.
Mittels Division mit Rest lassen sich solche Linearkombination bestimmen, die sukzessive immer kleiner werden, bis der größte gemeinsame Teiler einfach abgelesen werden kann. Dafür wird eine Folge $(r_n)_{n\in\mathbb{N}}$ von immer kleiner werdenden Resten gebildet beginnend mit $r_0 = a$ und $r_1 = b$. Anschließend wird eine Division mit Rest für diese Zahlen durchgeführt. Gesucht sind also $q_1\in\mathbb{Z}$ und $r_2\in\mathbb{Z}$, sodass
- $0\leq r_2 < b$ und
- $a = q_1\cdot b + r_2$
gelten. Und werden $a$ und $b$ wie oben beschrieben als Reste $r_0$ und $r_1$ geschrieben, führt das zu der Gleichung
\[r_0 = q_1\cdot r_1 + r_2,\]
die dann sehr leicht verallgemeinert werden kann, um den letzten Schritt zu iterieren: Im nächsten Schritt werden $q_2\in\mathbb{Z}$ und $r_3\in\mathbb{Z}$ mit $0\leq r_3 < r_2$ und $r_1 = q_2\cdot r_2 + r_3$ gesucht, und allgemein dann zu zwei gegebenen Resten $r_i$ und $r_{i+1}$ ein $q_{i+1}\in\mathbb{Z}$ und ein $r_{i+2}\in\mathbb{Z}$ mit $0\leq r_{i+2} < r_{i+1}$ und $r_i = q_{i+1}\cdot r_{i+1} + r_{i+2}$. Damit ergibt sich eine Folge von Divisionen mit Rest:
\[r_0 = q_1\cdot r_1 + r_2\]
\[r_1 = q_2\cdot r_2 + r_3\]
\[r_2 = q_3\cdot r_3 + r_4\]
\[\vdots\]
\[r_i = q_{i+1}\cdot r_{i+1} + r_{i+2}\]
\[r_{i+1} = q_{i+2}\cdot r_{i+2} + r_{i+3}\]
\[\vdots\]
Da die Reste so konstruiert wurden, dass $r_{i+1} < r_i$ für alle $i\in\mathbb{N}$ gilt, muss einer der Reste irgendwann einmal gleich Null sein. Sprich, es wird einmal ein Index $N$ erreicht, sodass \[r_{N - 1} = q_N\cdot r_N + 0\] gilt. Und dieser letzte Rest $r_N$ ist dann der gesuchte $\mathrm{ggT}(a,b)$. Der Grund dafür ist die Identität $\mathrm{ggT}(a,b) = \mathrm{ggT}(a + \mu b,b)$, die oben bereits erwähnt wurde: Hier impliziert sie im ersten Schritt, dass \[\mathrm{ggT}(a,b) = \mathrm{ggT}(a - q_0 b,b).\] In Resteschreibweise übertragen und iteriert führt das zur Gleichungskette \[\mathrm{ggT}(r_0, r_1) = \mathrm{ggT}(r_2, r_1) = \mathrm{ggT}(r_2, r_3) = \cdots = \mathrm{ggT}(r_i, r_{i+1}) = \cdots = \mathrm{ggT}(r_{N-1}, r_N).\]
Und da $r_N$ ein Teiler von $r_{N-1}$ ist, ist
\[r_N=\mathrm{ggT}(r_{N-1}, r_N) = \cdots = \mathrm{ggT}(a, b).\]
Ein Beispiel
Abschließend noch ein konkretes Zahlenbeispiel für dieses Verfahren: Angenommen, es ist der $ggT$ von $144$ und $89$ zu bestimmen. Dazu wird eine sukzessive Division mit Rest durchgeführt, bis der Rest Null erreicht wird. Also:
\[144 = 1\cdot 89 + 55\]
\[89 = 1\cdot 55 + 34\]
\[55 = 1\cdot 34 + 21\]
\[34 = 1\cdot 21 + 13\]
\[21 = 1\cdot 13 + 8\]
\[13 = 1\cdot 8 + 5\]
\[8 = 1\cdot 5 + 3\]
\[5 = 1\cdot 3 + 2\]
\[3 = 1\cdot 2 + 1\]
\[2 = 2\cdot 1 + 0\]
Es wurde ein Punkt erreicht, an dem ein Rest gleich $0$ ist. Damit ist der letzte Rest, der davor berechnet wurde, der gesuchte $ggT$. Hier also $1$; die beiden Zahlen $144$ und $89$ sind also teilerfremd. Insbesondere ist das auch der $ggT$ aller aufeinanderfolgenden Reste:
\[\mathrm{ggT}(144,89) = \mathrm{ggT}(55,89) = \mathrm{ggT}(55,34) = \mathrm{ggT}(21,34) = \mathrm{ggT}(21,13)\]
\[ = \mathrm{ggT}(8,13) = \mathrm{ggT}(8,5) = \mathrm{ggT}(3,5) = \mathrm{ggT}(3,2) = \mathrm{ggT}(2,1) = 1\]