Доказательство Алгоритма Евклида(Эвклида) для нахождения НОДа. Если НОД(a,b)=d при a>b, то НОД(a-b,b)=d

Предыдущий
вопрос Следующий
вопрос

Доказательство:

Пусть a = bq + r, где q - целое число, а r - остаток от деления a на b.

Так как НОД(a, b) = d, то a = md и b = nd, где m и n - наименьшие натуральные числа, такие что d = ma + nb.

Тогда а - b = bq + r - b = b(q - 1) + r.

Таким образом, (a - b) = b(q - 1) + r = nd(q - 1) + r = n(q - 1)d.

Так как НОД(a, b) = d, то НОД(b, r) = d.

Поэтому НОД(a - b, b) = d.

Таким образом, мы доказали, что если НОД(a, b) = d, то НОД(a - b, b) = d.