Die Reste seien mit
bezeichnet. Wenn
ein gemeinsamer Teiler von
und von
ist, so zeigt die Beziehung
-

dass
auch ein Teiler von
und damit ein gemeinsamer Teiler von
und von
ist. Die Umkehrung folgt genauso. Daraus folgt mit der Gleichungskette
-

dass der Algorithmus den größten gemeinsamen Teiler von
und
berechnet.