\newcommand{\ggt}{\operatorname{ggt}}
\newcommand{\NN}{\mathbb{N}}


\begin{slide}{Größter gemeinsamer Teiler}

Definitionen:
\begin{itemize}
\item
$t$ ist Teiler von $a$: \quad  $t \mid a \iff \exists k \in\NN : t \cdot k = a$
\item
Menge aller gemeinsamen Teiler von  $a$ und $b$: 

$T(a,b)=\{ t : t \mid a \wedge t \mid b \}$.
\item
größter gemeinsamer Teiler von $a$ und $b$

$\ggt(a,b)=t \iff t\in T(a,b) \wedge \forall s\in T(a,b): s\mid t$
\end{itemize}

Eigenschaften:
\begin{itemize}
\item $\ggt(a,a)=a$
\item $\ggt(a,b)=\ggt(a,a-b)$
\end{itemize}


\end{slide}


\begin{slide}{(Einfacher) Euklidischer Algorithmus}


\begin{verbatim}
Eingabe: natürliche Zahlen a, b.
// Vorbedingung: a = A und b = B
// Invariante: ggt(a,b) = ggt(A,B)
while (a ungleich b) {
     if (a > b) {
         ...
     } else {
         ...
     }
}
// Nachbedingung: a = ggt(A,B)
Ausgabe: a
\end{verbatim}
  
\end{slide}

\begin{slide}{(Erweiterter) Euklidischer Algorithmus}

\begin{verbatim}
Eingabe: natürliche Zahlen a, b.
// Vorbedingung: a = A und b = B
nat c = 1, nat d = 0; nat e = 0; nat f = 1;
// Invariante: ggt(a,b) = ggt(A,B)
//   und A*c + B*d = a  und  A*e + B*f = b
while (a ungleich b) {
     if (a > b) {
         ...
     } else {
         ...
}    }
// Nachbedingung: A*c + B*d = ggt(A,B)
Ausgabe: c, d
\end{verbatim}
  
\end{slide}
