alg10
10. Докажите, что для любых натуральных чисел a, b, a > b верно: НОД(a, b) = НОД(a – b, b).
Решение (смотри также разбор в тетради)
Пусть d общий делитель для a и для b, тогда a=pd b=qd или a-b=(p-q)d
Видим, что d является делителем a-b
Ну значит наибольший делитель для a и b будет общим делителем и для (a-b,b)
Но вдруг есть еще больший делитель, чем наш d
Для этого надо доказать, обратное, что любой делитель для пары (a-b), b будет делителем и для a, b в аналогично тому как это сделал выше если a-b=sd b=qd, то a=(a-b)+b=sd+qd
Откуда видим, что и для пары (a,b) и для пары ((a-b),b) делители одни и те же, естественно наибольший из них тот же.
Это же все тот же алгоритм Евклида, как его знали древние, а не через остатки.