Задача 105090
|
|
 |
Условие
Наибольший общий делитель натуральных чисел m и n равен 1. Каково наибольшее возможное значение НОД(m + 2000n, n + 2000m)?
Решение
Пусть a = 2000m + n, b = 2000n + m, d = НОД(a, b). Тогда d делит также числа 2000a – b = (2000² – 1)m и 2000b – a = (2000² – 1)n. Поскольку m и n взаимно просты, то d делит 2000² – 1.
С другой стороны, при m = 2000² – 2000 – 1, n = 1, получаем a = (2000² – 1)(2000 – 1), b = 2000² – 1 = d.
Ответ
3999999.
