Um zu zeigen, daß der Gesamtalgorithmus korrekt arbeitet, muß gezeigt werden, daß die drei Aufrufe
wie gewünscht in 
, in 
und in 
ablegen. Dies ist trivial: Die
Korrektheit der Berechnung des ggT nach dem euklidischen Algorithmus wurde oben bereits gezeigt. Daher muß diese
Zuweisung zum korrekten Ergebnis in führen. Der Zusammenhang zur Berechnung der Faktoren und ist
elementar und wurde bereits unter 
hergeleitet und bewiesen. Daher müssen auch sie das korrekte Ergebnis
erzeugen, da in der ggT von 
und 
richtig vorliegt.