euklidischer Algorithmus
1. Definition
Sei \(R\) ein euklidischer Ring Sei \(r_0 \coloneqq a\), \(r_1 \coloneqq b\) so liefert der Algorithmus:
\begin{align*} r_0 =& r_1 \cdot q_1 + r_2 \\ & \vdots \\ r_{i+1} =& r_{i} \cdot q_{i} + r_{i-1} \\ & \vdots \\ r_{n-2} =& r_{n-1} \cdot q_{n-1} + r_{n} \\ r_{n-1} =& r_{n} \cdot q_{n} + 0 \\ \end{align*}Wobei \(q_{i+1}, r_{i+2}\) die Bedingung für die euklidische Division erfüllen Dann ist der größter gemeinsamer Teiler \(r_{n} \neq 0\) mit \(r_{n+1} = 0\)
2. Beweis
2.1. Teiler
\(r_{n}\) teilt \(r_{n-1}\). Damit teilt \(r_n\) auch \(r_{n-2}\) wegen \(r_{n-2} = r_{n-1} \cdot q_{n-1} + r_n = r_{n} \cdot q_{n-2} q_{n-1} + r_n\) Analog für \(r_{n-3},...,r_0\) und damit auch \(r_{0} = a, r_1 = b\)
2.2. größter Teiler
Sei \(g \in R\) mit \(g \mid a, g \mid b\), so gilt \(g \mid r_0, g \mid r_1\). Damit gilt dann auch \(r_2 = r_0 - r_1 \cdot q_1\) bzw. \(g \mid r_2\) und allgemein
\begin{align*} r_{i+2} =& r_{i} - r_{i} \cdot q_i \\ g \mid r_{i+2} \end{align*}und insbesondere auch \(g \mid r_{n}\)