Юл
Юлия
Помогите пожалуйста найти наибольший общий делитель
Наибольший общий делитель (НОД) натуральных чисел m и n равен 1. Каково наибольшее возможное значение НОД чисел m+2000n и n+2000m?
Наибольший общий делитель (НОД) натуральных чисел m и n равен 1. Каково наибольшее возможное значение НОД чисел m+2000n и n+2000m?
Наибольший общий делитель (НОД) натуральных чисел m и n равен 1.
Каково наибольшее возможное значение НОД чисел m+2000n и n+2000m?
Ответ: 20002-1.
Пусть a=2000m+n, b=2000n+m, d - наибольший общий делитель a и b.
Тогда d делит также числа
2000a-b=(20002-1)m и 2000b-a=(20002-1)n.
Поскольку m и n взаимно просты, то d делит 20002-1.
С другой стороны, при m=20002-2000-1, n=1,
получаем a=(20002-1)(2000-1), b=20002-1=d.