De ce algoritmul lui Euclid păstrează cel mai mare divizor comun?
Dacă , un divizor comun al lui a și b divide și ; reciproc, un divizor comun al lui b și r divide a.
Exemplu explicat
; ; . Ultimul rest nenul este 6, deci .
Greșeala de evitat
Răspunsul este ultimul rest nenul, nu ultimul rest, care este zero.
