nod 5

Ответ от Наталья[гуру]
Думаю, что Вы знаете алгоритм Евклида нахождения НОД (x,y).
Идея этого алгоритма основана на том свойстве, что если x>y, то НОД (x, y) = НОД (x - y, y). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.
Легко доказать это свойство. Пусть k - общий делитель x и y (x> y). Это значит, что x = mk, y = nk, где m, n - натуральные числа, причем m > n. Тогда x-y=k(m-n), откуда следует, что k - делитель числа x-y. Значит, все общие делители чисел x и y являются делителями их разности x - y, в том числе и наибольший общий делитель.
Для нашей задачи
НОД (5a+3b,13a+8b)=НОД (5a+3b,8a+5b)=НОД (5a+3b,3a+2b)=
=НОД (2a+b,3a+2b)=НОД (2a+b,a+b)=НОД (a,a+b)=НОД (a,b)