Задача 60496

Тема:    [ НОД и НОК. Взаимная простота ]

Сложность: 3 Классы: 8,9,10

Условие

Докажите, что  (5a + 3b, 13a + 8b) = (a, b).

Подсказка

8(5a + 3b) – 3(13a + 8b) = a,  5(13a + 8b) – 13(5a + 3b) = b.

Замечания

Можно также применить алгоритм Евклида:   (13a + 8b, 5a + 3b) = (5a + 3b, 3a + 2b) = (3a + 2b, 2a + b) = (2a + b, a + b) = (a + b, a) = (a, b).

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	2
Название	Алгоритм Евклида
Тема	Алгоритм Евклида
задача
Номер	03.044