\begin{slide}{Hilfsmittel: erweiterter Euklid}

Satz: wenn $g = \ggT(a,b)$,
dann gibt es Zahlen $c,d$ mit $ac + bd=g$.

\begin{verbatim}
c = 1; d = 0; e = 0; f = 1;
while (b > 0) {
   // c*a0 + d*b0 = a und e*a0 + f*b0 = b
   q = a / b; r = a % b; // resultat, rest
   a = b; b = r;
   e' = c - q*e; c = e; e = e';
   f' = d - q*f; d = f; f = f';
}

\end{verbatim}

\begin{verbatim}
40 : 7 = 5 R 5    5 = 40 - 5*7
 7 : 5 = 1 R 2    2 = 7  -   5 = -40 + 6*7
 5 : 2 = 2 R 1    1 = 5  - 2*2 = 5*40 - 17*7
\end{verbatim}


\end{slide}
