V
Nehmen wir mal an, daß a!=b ist. Wenn sie gleich sind, wissen wir den GGT schon.
Nehmen wir mal weiter an, daß a größer als b ist. Wenn das nicht der Fall ist, vertauschen wir die beiden vorher mal.
Der mathematische Trick:
Wenn a und b durch x teilbar sind, dann ist auch a%b durch x teilbar.
a%b ist kleiner als b.
Auf der Suche nach dem GGT(26,16) verwende ich den Trick und sage mir, der GGT(26,16) ist ja gleich dem GGT(16,26%16) also GGT(16,10).
Das mache ich gleich nochmal. GGT(16,10)=GGT(10,6).
Und nochmal: GGT(10,6)=GGT(6,4). GGT(6,4)=GGT(4,2). GGT(4,2)=GGT(2,0).
oh, b ist 0 geworden. weil die 4 durch 2 teilbar war. ja, dann ist die 2 der GGT(4,2). Deswegen also die Abfrage, ob b gleich 0 ist.