Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля.
Смысл алгоритма заключается в том, что два любых числа a и b могут быть представлены в следующей форме:
- Код: выделить все
a=q_0*b+r_1
b=r_1*q_1+r_2
r_1=r_2*q_2+r_3
…
r_(n-2)=r_(n-1)*q_(n-1)+r_n
r_(n-1)=r_n*q_n
НОД(a,b)=r_n
Существование таких r и q эквивалентно возможности деления целого числа на другое целое не нулевое число с остатком.
Верность последнего утверждения следует из следующего равенства:
- Код: выделить все
НОД(a,b)=НОД(b,r),если a=b*q+r.
Докажем это
Необходимость
Пусть существует такое k, которое является делителем и числа a и числа b, т.е.:
- Код: выделить все
a=k*t, b=k*s.
Но тогда, по определению числа r:
- Код: выделить все
r=a-b*q=k(t-b*s),
r тоже делится на k.
Достаточность
Если b,r делится на некоторое k, то их взвешенная целыми коэффициентами сумма тоже делится на k.