\ANG{
{\bf Die Kettendivision (Euklidscher Algorithmus)}
\begin{enumerate}
\item \GF{Ist $t$ ein gemeinsamer Teiler der Zahlen $a$ und $b$ mit $a>b$, dann ist $t$ auch ein
  Teiler von $r$, wobei $r$ der Rest der Division von $a$ durch $b$ ist 
  ($a\,:\,b=x\,\text{Rest}\,r$).}\\
  Begr"unde allgemein die Richtigkeit dieser Aussage. Zeige die G"ultigkeit dieser Aussage 
  am Beispiel $a=1386$, $b=588$ und $t=21$.
\item Es gilt folgender Satz:
  \begin{center}
    \fbox{\parbox[t]{12cm}{F"ur $a>b$ ist $\ggT(a,b)=\ggT(b,r)$, wobei
    $r$ der Rest der Division von $a$ durch $b$ ist. }} 
  \end{center}
  Zeige die G"ultigkeit dieses Satzes am Beispiel $a=1386$ und $b=588$.
\item Warum ist jede nat"urliche Zahl ein Teiler von 0? Zeige, dass $\ggT(b,0)=b$
  gilt. 
\end{enumerate}
Mit Hilfe der bisherigen Ergebnisse suchen wir jetzt den ggT der Zahlen 589 und 527, den
wir mit $x$ bezeichnen. Wir teilen die gr"o"sere durch die kleinere Zahl:

\centerline{$589\,:\,527=1\,\text{Rest}\,62$} 

Nach dem Satz aus Teilaufgabe (b) gilt

\centerline{$x=\ggT(589,\,527)=\ggT(527,\,62)$}

Die Aufgabe, den ggT der Zahlen 589 und 527 zu finden, ist somit gleichwertig zu der 
Aufgabe, den ggT der Zahlen 527 und 62 zu finden. Die Aufgabe hat sich vereinfacht, da die
Zahlen kleiner geworden sind. Also wenden wir die gleiche Methode noch einmal an:

\centerline{$527\,:\,62=8\,\text{Rest}\,31\quad\DANN\quad 
  x=\ggT(527,\,62)=\ggT(62,\,31)$}

Und noch einmal:

\centerline{$62\,:\,31=2\,\text{Rest}\,0\quad\DANN\quad 
  x=\ggT(62,\,31)=\ggT(31,\,0)\,\stackrel{\text{wegen (c)}}{=}\,31$}

Zusammenfassung der Berechnung des ggT von 589 und 527:
\begin{alignat*}{2}
 589\,&:\,527 &= 1\,\text{Rest}\,62 &\\
  527\,&:\,62 &= 8\,\text{Rest}\,31 &\\
   62\,&:\,\boxed{31} &= 2\,\text{Rest}\,0 &\quad\DANN\quad 
   \ggT(589,\,527)=\underline{\underline{31}}
\end{alignat*}
\begin{enumerate}
\item[(d)] Berechne: ggT(2173,\,1271)
\item[(e)] K"urze soweit wie m"oglich: $\D \frac{2697}{4611}$ 
\end{enumerate}

}
\LSG{
\begin{enumerate}
\item $a\,:\,b=x\,\text{Rest}\,r\quad\DANN\quad a=b\cdot x+r\quad\DANN\quad r=a-b\cdot
  x$\\
  Da $t$ ein Teiler von $a$ und von $b$ ist, gilt $a=n\cdot t$ und $b=m\cdot t$, d.h. 
  $r=n\cdot t-m\cdot t\cdot x=(n-m\cdot x)\cdot t$.\\
  $1386=66\cdot 21$,\quad $588=28\cdot 21$,\quad $1386\,:\,588=2\,\text{Rest}\,210$
\item $\ggT(1386,\,588)=42$,\quad $\ggT(588,\,210)=42$
\item $0\,:\,n=0$.\quad Da $b$ der gr"o"ste Teiler von $b$ und auch ein Teiler von 0 ist,
  ist $b$ der $\ggT(b,0)$.
\item \rule{0mm}{0mm}
\vspace{-14mm}

\begin{alignat*}{4}
 2173\,&:\,1271 &&= 1\,&&\text{Rest}\,902 &&\\
 1271\,&:\,902 &&= 1\,&&\text{Rest}\,369 &&\\
 902\,&:\,369 &&= 2\,&&\text{Rest}\,164 &&\\
 369\,&:\,164 &&= 2\,&&\text{Rest}\,41 &&\\
 164\,&:\,\boxed{41} &&= 4\,&&\text{Rest}\,0 &&\quad\DANN\quad 
   \ggT(2173,\,1271)=\underline{\underline{41}}
\end{alignat*}
\item \rule{0mm}{0mm}
\vspace{-14mm}

\begin{alignat*}{4}
 4611\,&:\,2697 &&= 1\,&&\text{Rest}\,1914 &&\\
 2697\,&:\,1914 &&= 1\,&&\text{Rest}\,783 &&\\
 1914\,&:\,783 &&= 2\,&&\text{Rest}\,348 &&\\
 783\,&:\,348 &&= 2\,&&\text{Rest}\,87 &&\\
 348\,&:\,\boxed{87} &&= 4\,&&\text{Rest}\,0 &&\quad\DANN\quad 
   \ggT(4611,\,2697)=\underline{\underline{87}}
\end{alignat*}
\[\frac{2697}{4611}=\frac{2697\,:\,87}{4611\,:\,87}=\frac{31}{53}\]
\end{enumerate}
}