Aufgabe 3: Euklidischer Algorithmus

Aufgabenstellung

Der euklidische Algorithmus für x, y ∈ ℤ kann folgendermaßen formuliert werden:

ggT(x, y)  =  
        ggT(|x|, |y|) 	falls x < 0 oder y < 0
ggT(x, y)  =  ggT (y, x)     	falls x < y
ggT(x, 0)  =  x
ggT(x, y)  =  ggT (y, x mod y)

Programmieren Sie den euklidischen Algorithmus und testen Sie ihn an zufälligen 1000-stelligen Zahlen.

Hilfestellung

Wie man eine rekursive Prozedur in Mathematica programmiert, sieht man hier am Beispiel der Fakultätsfunktion

Fak[n_] := n Fak[n - 1]
Fak[0] := 1

Die erste Zeile ist die eigentliche Rekursion und die zweite Zeile ist das Abbruchkriterium. 
7! ist z.B.

Fak[7]

Zufallszahlen kann man mit Random erzeugen

?Random