Euklidischer Algorithmus

Der Euklidische Algorithmus ist einer der ältesten und berühmtesten Algorithmen überhaupt. Er dient zur Bestimmung des größten gemeinsamen Teilers zweier positiver ganzer Zahlen $\mathit{a}$ und $\mathit{b}$ mit $\mathit{a}>\mathit{b}$.

Der Algorithmus funktioniert wie folgt:

1. Man dividiert $\mathit{a}$ durch $\mathit{b}$ und erhält einen Rest $\mathit{r}$
2. Ist $\mathit{r}=0$, ist $(\mathit{a},\mathit{b})=\mathit{b}$.
3. Ist $\mathit{r}\ne 0$, wird $\mathit{a}$ der Wert von $\mathit{b}$ zugewiesen und $\mathit{b}$ der Wert von $\mathit{r}$. Man wiederhole dann den Zyklus ab Schritt 1 bis der Rest $0$ ist. Der entsprechende Wert von $\mathit{b}$ ist dann der gesuchte $(\mathit{a},\mathit{b})$.

Man setzt ${\mathit{r}}_{-1}=\mathit{a},{\mathit{r}}_0=\mathit{b}$. Dann ist

$$\begin{array}{lrcl}\text{Division von}{\mathit{r}}_{-1}\text{durch}{\mathit{r}}_0:& {\mathit{r}}_{-1}& =& {\mathit{q}}_1{\mathit{r}}_0+{\mathit{r}}_1\text{mit}0<{\mathit{r}}_1<{\mathit{r}}_0\\ \text{Division von}{\mathit{r}}_0\text{durch}{\mathit{r}}_1:& {\mathit{r}}_0& =& {\mathit{q}}_2{\mathit{r}}_1+{\mathit{r}}_2\text{mit}0<{\mathit{r}}_2<{\mathit{r}}_1\\ \text{Division von}{\mathit{r}}_1\text{durch}{\mathit{r}}_2:& {\mathit{r}}_1& =& {\mathit{q}}_3{\mathit{r}}_2+{\mathit{r}}_3\text{mit}0<{\mathit{r}}_3<{\mathit{r}}_2\\ ⋮& ⋮& & ⋮\\ \text{Division von}{\mathit{r}}_{\mathit{i}-2}\text{durch}{\mathit{r}}_{\mathit{i}-1}:& {\mathit{r}}_{\mathit{i}-2}& =& {\mathit{q}}_{\mathit{i}}{\mathit{r}}_{\mathit{i}-1}+{\mathit{r}}_{\mathit{i}}\text{mit}0<{\mathit{r}}_{\mathit{i}}<{\mathit{r}}_{\mathit{i}-1}\\ ⋮& ⋮& & ⋮\\ \text{Division von}{\mathit{r}}_{\mathit{n}-3}\text{durch}{\mathit{r}}_{\mathit{n}-2}:& {\mathit{r}}_{\mathit{n}-3}& =& {\mathit{q}}_{\mathit{n}-1}{\mathit{r}}_{\mathit{n}-2}+{\mathit{r}}_{\mathit{n}-1}\text{mit}0<{\mathit{r}}_{\mathit{n}-1}<{\mathit{r}}_{\mathit{n}-2}\\ \text{Division von}{\mathit{r}}_{\mathit{n}-2}\text{durch}{\mathit{r}}_{\mathit{n}-1}:& {\mathit{r}}_{\mathit{n}-2}& =& {\mathit{q}}_{\mathit{n}}{\mathit{r}}_{\mathit{n}-1}+{\mathit{r}}_{\mathit{n}},\end{array}$$

wobei ${\mathit{r}}_{\mathit{n}}=0$. Die Reste bilden eine Reihe von abnehmenden natürlichen Zahlen

$${\mathit{r}}_1>{\mathit{r}}_2>{\mathit{r}}_3\dots >{\mathit{r}}_{\mathit{n}-1}>{\mathit{r}}_{\mathit{n}}=0$$

und so erhält man irgendwann einen Nullwert ${\mathit{r}}_{\mathit{n}}=0$. Der gesuchte $(\mathit{a},\mathit{b})$ ist ${\mathit{r}}_{\mathit{n}-1}$.

Der Algorithmus funktioniert, da wegen des obigen Satzes

$$(\mathit{a},\mathit{b})=(\mathit{b},{\mathit{r}}_1)=({\mathit{r}}_1,{\mathit{r}}_2)=({\mathit{r}}_2,{\mathit{r}}_3)=\dots =({\mathit{r}}_{\mathit{n}-2},{\mathit{r}}_{\mathit{n}-1})=({\mathit{r}}_{\mathit{n}-1},0)={\mathit{r}}_{\mathit{n}-1}.$$

ist.

Beispiel

Bestimmung von $(2782,2249)$:

$$\begin{array}{lrcl}\text{Division von}2782\text{durch}2249:& 2782& =& 1\cdot 2249+533\\ \text{Division von}2249\text{durch}533:& 2249& =& 4\cdot 533+117\\ \text{Division von}533\text{durch}117:& 533& =& 4\cdot 117+65\\ \text{Division von}117\text{durch}65:& 117& =& 1\cdot 65+52\\ \text{Division von}65\text{durch}52:& 65& =& 1\cdot 52+13\\ \text{Division von}52\text{durch}13:& 52& =& 4\cdot 13+0\end{array}$$

Der letzte Rest, der nicht $0$ ist, ist $13$. Also ist $(2782,2249)=13$. Es gilt

$$(2782,2249)=(2249,533)=(533,117)=(117,65)=(65,52)=(52,13)=(13,0)=13.$$

Kettenbrüche

Schreibt man die Zeilen des obigen Beispiels in der Form

$$\begin{array}{rcl}\frac{2782}{2249}& =& 1+\frac{533}{2249}\\ \frac{2249}{533}& =& 4+\frac{117}{533}\\ \frac{533}{117}& =& 4+\frac{65}{117}\\ \frac{117}{65}& =& 1+\frac{52}{65}\\ \frac{65}{52}& =& 1+\frac{13}{52}\\ \frac{52}{13}& =& 4,\end{array}$$

führt das zu einer ungewohnten Art der Darstellung eines Bruches:

$$\begin{array}{rcl}\frac{2782}{2249}& =& 1+\frac{533}{2249}=1+\frac{1}{\frac{2249}{533}}=1+\frac{1}{4+\frac{117}{533}}=1+\frac{1}{4+\frac{1}{\frac{533}{117}}}=1+\frac{1}{4+\frac{1}{4+\frac{65}{117}}}=1+\frac{1}{4+\frac{1}{4+\frac{1}{\frac{117}{65}}}}\\ & =& 1+\frac{1}{4+\frac{1}{4+\frac{1}{1+\frac{52}{65}}}}=1+\frac{1}{4+\frac{1}{4+\frac{1}{1+\frac{1}{\frac{65}{52}}}}}=1+\frac{1}{4+\frac{1}{4+\frac{1}{1+\frac{1}{1+\frac{13}{52}}}}}=1+\frac{1}{4+\frac{1}{4+\frac{1}{1+\frac{1}{1+\frac{1}{4}}}}}.\end{array}$$

Also ist

$$\frac{2782}{2249}=1+\frac{1}{4+\frac{1}{4+\frac{1}{1+\frac{1}{1+\frac{1}{4}}}}}=[1,4,4,1,1,4]\text{abgekürzt}.$$

Die rechte Seite der Gleichung ist ein sogenannter Kettenbruch, d.h. ein Bruch, dessen Nenner immer ein weiterer Bruch ist. Bei einer rationalen Zahl wie hier bricht die Kettenbruchentwicklung ab.

In Form von den Quotienten ${\mathit{q}}_{\mathit{i}}$ im Euklidischen Algorithmus ist die Kettenbruchentwicklung des Bruches $\mathit{a}/\mathit{b}$ gegeben durch

$$\frac{\mathit{a}}{\mathit{b}}={\mathit{q}}_1+\frac{1}{{\mathit{q}}_2+\frac{1}{{\mathit{q}}_3+\dots }}=[{\mathit{q}}_1,{\mathit{q}}_2,\dots ,{\mathit{q}}_{\mathit{n}}]{\mathit{q}}_{\mathit{i}}\in {\mathbb{N}}_0,{\mathit{q}}_{\mathit{i}}\ge 1\text{für}1<\mathit{i}<\mathit{n}\text{und}{\mathit{q}}_{\mathit{n}}\ge 2.$$