\documentclass[a4paper,11pt]{article}
\usepackage[german]{babel}
\usepackage{epsfig}
\usepackage{verbatim}
\newcommand{\url}[1]{\nobreak{\it#1}}
\newcommand{\tilda}{\def\~{}}
\newcommand{\grad}{\ensuremath{^\circ}}
\usepackage{german}
%\usepackage{mfpic}
\usepackage{graphicx}
\usepackage{graphicx}
\thispagestyle{empty}
\selectlanguage{\austrian}
\begin{document}
\section{Euklidischer Teileralgorithmus}

Ziel ist es, den gr\"ossten gemeinsamen Teiler (ggt, gcd (greatest common
divisor)) zweier Zahlen zu finden, die nicht relativ prim sind. Dazu zieht
Euklid (\~{} 300 vC) folgende beiden Beobachtungen heran:

\begin{enumerate} 
\item 
{f\"ur zwei ganze Zahlen gilt:} 

$$ b | a \Rightarrow ggt(a,b) = b $$

Begr\"undung: keine Zahl kann durch eine Zahl geteilt werden, die gr\"osser
ist als die Zahl selbst.

\item 
{Rekursionsschritt:}

$$ a = b t + r \Rightarrow ggt(a,b) = ggt(b,r) $$
(f\"ur $ t, r \in \!N $ )
\\

Jede Zahl, die a und b teilt, ist auch ein Divisor von r. Daher teilt
ggt(a,b) auch r ($ggt(a,b) | r$), nicht nur b, sodass $ggt(a,b) \le ggt(b,r)$,
ebenso $ggt(a,b) \le ggt(a,r)$. Wenn nun f\"ur den n\"achsten
Schritt $a = b$ und $b = r$ gesetzt wird, kann das Verfahren so lange
fortgesetzt werden, bis gilt $b|a$, also der Divisionsrest {\tt a \% b == 0}.
\end{enumerate} 

In der urpsruenglichen Version subtrahierte Euklid jeweils a von b, der
Algorithmus waere also dann:
\begin{enumerate} 
\item wenn {\tt b > a}, dann vertausche {\tt a} und {\tt b}
\item wenn {\tt a} durch {\tt b} dividierbar ist, dann Ergebnis
{\tt ggt(a,b) == b} {\bf ENDE}
\item subtrahiere {\tt b} von {\tt a}
\item gehe zu {\bf 1.}
\end{enumerate} 

\subsection{Beispiel}

\begin{enumerate} 
\item $a = 9690, b = 3825 \Rightarrow r = 2040$
\item $a = 3825, b = 2040 \Rightarrow r = 1785$
\item $a = 2040, b = 1785 \Rightarrow r = 255$
\item $a = 1785, {\bf b = 255} \Rightarrow r = 0$
\end{enumerate} 
{\tt ggt(9690,2040) == 255}

\section{graphische \"Uberlegung}
\includegraphics[width=\textwidth]{ggts.eps}

\subsection{Schreibweise}
\begin{tabular}[l]{l@{\hspace{1cm}}l}
$b|a$       & b teilt a ({\tt a \% b == 0}) \\
$ggt(a,b)$  & gr\"osster gemeinsamer Teiler
\end{tabular}
\begin{flushright}
{\small copyleft 2006 Alexander Oelzant}
\end{flushright}
\end{document}