de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Euklidischer Algorithmus
Nachlesen

Euklidischer Algorithmus

Der euklidische Algorithmus ist ein Algorithmus aus dem Gebiet der Zahlentheorie, mit dem sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen lässt. Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt. Der größte gemeinsame Teiler kann alternativ auch über die Primfaktorzerlegungen der Zahlen ermittelt werden. Sind diese nicht bekannt, so ist der euklidische Algorithmus im Allgemeinen jedoch deutlich effizienter.

Inhalt

Beschreibung des Verfahrens

Gegeben seien zwei natürliche Zahlen $a$ und $b$ mit $b \leq a$, deren größter gemeinsamer Teiler $\ggT(a,b)$ bestimmt werden soll. Hierzu wird zunächst eine Zerlegung mit Rest bestimmt, d.h., es werden ganze Zahlen $q_1,r_1$ mit $0 \leq r_1 \lt b$ bestimmt, für die gilt:

\[ a = q_1 \cdot b + r_1. \]

Die Grundidee des euklidischen Algorithmus beruht auf der Tatsache, dass $\ggT(a,b) = \ggT(b,r_1)$ gilt. Anstelle des größten gemeinsamen Teilers von $a$ und $b$ kann also auch der größte gemeinsame Teiler von $r_0=b$ und $r_1$ berechnet werden. Hierzu wird wieder eine Zerlegung mit Rest vorgenommen:

\[ r_0 = q_2 \cdot r_1 + r_2. \]

Wie zuvor gilt $\ggT(r_0,r_1) = \ggT(r_1,r_2)$ und somit auch $\ggT(a,b) = \ggT(r_1,r_2)$. Dieses Verfahren wird nun solange wiederholt, bis der Rest $0$ auftritt.

\begin{align*} r_1 &= q_3 \cdot r_2 + r_3 \\[0.5em] &\ \ \vdots \\[0.5em] r_{n-1} &= q_{n+1} \cdot r_n + 0 \end{align*}

Die letzte Zeile bedeutet, dass $r_{n-1}$ ein ganzzahliges Vielfaches von $r_n$ ist – hieraus folgt direkt $\ggT(r_{n-1},r_n) = r_n$ und somit $\ggT(a,b)=r_n$.

Beispiele

Beispiel 1

Es soll der größte gemeinsame Teiler von $564$ und $235$ bestimmt werden. Mit dem euklidischen Algorithmus ergibt sich:

\begin{align*} 564 &= 2 \cdot 235 + 94 \\[0.5em] 235 &= 2 \cdot 94 + {\color{CornflowerBlue} 47} \\[0.5em] 94 &= 2 \cdot {\color{CornflowerBlue} 47} + 0 \end{align*}

Es gilt $\ggT(564,235)=47$. Der größte gemeinsame Teiler \({\color{CornflowerBlue} 47}\) kann in der letzten oder in der vorletzten Zeile direkt abgelesen werden.

Beispiel 2

Es soll der größte gemeinsame Teiler von $42$ und $23$ bestimmt werden. Mit dem euklidischen Algorithmus ergibt sich:

\begin{align*} 42 &= 1 \cdot 23 + 19 \\[0.5em] 23 &= 1 \cdot 19 + 4 \\[0.5em] 19 &= 4 \cdot 4 + 3 \\[0.5em] 4 &= 1 \cdot 3 + {\color{CornflowerBlue} 1} \\[0.5em] 3 &= 3 \cdot {\color{CornflowerBlue} 1} + 0 \end{align*}

Es gilt $\ggT(42,23)=1$; die Zahlen $42$ und $23$ sind folglich teilerfremd. Der größte gemeinsame Teiler \({\color{CornflowerBlue} 1}\) kann in der letzten oder in der vorletzten Zeile direkt abgelesen werden.

Beweis

Gegeben seien zwei natürliche Zahlen $a$ und $b$ mit $a \geq b$ sowie zwei ganze Zahlen $q,r$ mit $0 \leq r \lt b$, so dass gilt:

\[ a = q \cdot b + r. \]

Der euklidische Algorithmus basiert auf der Grundannahme $\ggT(a,b) = \ggT(b,r)$, die direkt aus den beiden folgenden Eigenschaften resultiert, die im Anschluss bewiesenen werden.

\begin{align*} \text{(I)} &\quad \ggT(a,b) \leq \ggT(b,r) \\[0.5em] \text{(II)} &\quad \ggT(b,r) \leq \ggT(a,b) \end{align*}

Beweis von (I)

Der Wert $\ggT(a,b)$ ist sowohl ein Teiler von $a$ als auch ein Teiler von $b$. Unter Verwendung der Rechenregeln der Teilbarkeit gilt:

\[ \ggT(a,b) \mid a \ \wedge \ \ggT(a,b) \mid b \ \Rightarrow \ \ggT(a,b) \mid \underbrace{(a - q \cdot b)}_{=r} \]

Da $\ggT(a,b)$ ein Teiler von $a$ und $b$ ist, ist $\ggT(a,b)$ folglich auch ein Teiler von $r$. Da nicht bekannt ist, ob $b$ und $r$ noch größere gemeinsame Teiler besitzen, folgt hieraus

\[ \ggT(a,b) \leq \ggT(b,r). \]

Beweis von (II)

Umgekehrt handelt es sich bei $\ggT(b,r)$ sowohl um einen Teiler von $b$ als auch um einen Teiler von $r$. Es gilt

\[ \ggT(b,r) \mid b \ \wedge \ \ggT(b,r) \mid r \ \Rightarrow \ \ggT(b,r) \mid \underbrace{(q \cdot b + r)}_{=a} \]

Da $\ggT(b,r)$ ein Teiler von $b$ und $r$ ist, ist $\ggT(b,r)$ folglich auch ein Teiler von $a$. Da nicht bekannt ist, ob $a$ und $b$ noch größere gemeinsame Teiler besitzen, folgt hieraus

\[ \ggT(b,r) \leq \ggT(a,b). \]