====== Der Euklidischer Algorithmus ======

Der Euklidischer Algorithmus ist ein Verfahren zur Bestimmung des ggT (GrößterGemeinsamerTeilers) zweier Zahlen.
Er basiert auf der Modulorechnung.

Man nehme zwei Zahlen a & b, für die gilt a>=b\\

a  mod b  = r<sub>1</sub>\\
b  mod r<sub>1</sub> = r<sub>2</sub>\\
r<sub>1</sub> mod r<sub>2</sub> = r<sub>3</sub>\\
r<sub>2</sub> mod r<sub>3</sub> = r<sub>4</sub>\\
....usw.\\
bis \\
r<sub>n</sub> mod r<sub>n+1</sub> = 0\\
dann: r<sub>n+1</sub>->ggT\\

===== Beispiel =====


ggT(35,25)=?\\
\\
35 mod 25 = 10\\
25 mod 10 = 5\\
10 mod 5 = 0\\
\\
=> 5=ggT(35,25)\\

===== Erklärung =====
Der gesamte Algorithmus basiert auf der schlichten Tatsache, dass der Rest von a/b (hier: r<sub>1</sub>) und b den selben ggT haben wie a und b. Und damit auch auch den selben wie der Rest aus b/r<sub>1</sub> (hier: r<sub>2</sub>) und r<sub>1</sub> und so weiter und so fort. Also muss die Modulorechnung "alter" Divisor modulo "alter" Rest so lange fortgeführt werden, bis r<sub>n</sub> ohne Rest durch r<sub>n+1</sub> teilbar ist, weil dann r<sub>n+1</sub> automatisch der ggT von sich selbst und r<sub>n</sub> ist. Im Bsp ist dies bei r<sub>n</sub>=10 und r<sub>n+1</sub>=5 erreicht.