Bei Teil b) ist nach einer Funktion gefragt, die den größten gemeinsamen Teiler (ggT) für zwei Zahlen, a und b, berechnet. Also eine Abbildung, die zwei Zahlen auf eine andere Zahl abbildet:
Jetzt brauchen wir noch eine genaue Abbildungsvorschrift. Dazu rufen wir uns die mathematische Definition des ggT ins Gedächtnis:
Zu zwei natürlichen Zahlen a und b ist der ggT d die größte Zahl, sodass gilt: d teilt a und d teilt b.
Die Menge aller Zahlen, die a und b teilen, lässt sich formell so aufschreiben:
Jetzt musst Du noch kennzeichnen, dass Du das größte Element dieser Menge meinst. Dazu kann man eine bestimmte Funktion benutzen... Danach hast Du Deine gesuchte Abbildungsvorschrift.
Zur c): Damit der Algorithmus korrekt ist, muss Alg(a,b) für alle natürlichen a und b mit ggT(a,b) übereinstimmen. Also lautet der Satz: