Задача 32111

Темы:    [ НОД и НОК. Взаимная простота ] [ Линейная и полилинейная алгебра ]

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

Условие

Каков наибольший возможный общий делитель чисел  9m + 7n  и  3m + 2n,  если числа m и n не имеют общих делителей, кроме единицы?

Решение

  Любой общий делитель чисел  9m + 7n  и  3m + 2n  должен быть также делителем чисел  (9m + 7n) – 3(3m + 2n) = n  и  7(3m + 2n) – 2(9m + 7n) = 3m.  Поскольку числа m и n взаимно просты, то любой общий делитель чисел n и 3m должен быть делителем числа 3, то есть не может быть больше 3.
  Это значение возможно: при  m = 1,  n = 3   НОД(9m + 7n, 3m + 2n) = НОД(30, 9) = 3.

Ответ

3.

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

олимпиада
Название	Турнир им.Ломоносова
год/номер
Номер	12
Дата	1989
задача
Номер	10