Question

Подробно объясните. Докажите, что НОД ( a, b) = НОД (5a+3b, 13a+8b)

Answer 1

Ответ:

НОД (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)

Пошаговое объяснение:

Думаю, что ты знаешь алгоритм Евклида нахождения НОД (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)