Найдите максимальное возможное значение наибольшего общего делителя чисел 50n+9 и 84n+18, где n — произвольное целое число. задан 29 Ноя '12 19:28 tcaxes |
Посмотрите алгоритм Евклида
Дополнение. По алгоритму Евклида получим, что искомый НОД является делителем 72. Но одно из чисел нечетно, поэтому наибольший НОД равен 9. И это действительно возможно (при n = 0 или 9) отвечен 29 Ноя '12 20:04 DocentI Можно, конечно, просто умножить первое уравнение на 84, второе - на 50 и вычесть. Получим число (константу), которое делится на НОД. Но это только достаточное условие.
(30 Ноя '12 1:56)
DocentI
|
$%NOD(50n+9;84n+18)=NOD(50n+9;34n+9).$% При любом $%n=9k$% делителем последней пары будет число $%9$%. Что касается того, что это число наибольшее, нужно показать, что $%NOD(50k+1;34k+1)=1$%. Затем возможно нужно рассмотреть представление числа $%n$% в виде $%n=9k\pm i, i=0..4. $% отвечен 30 Ноя '12 19:44 Anatoliy 1
Можно проще. Искомый НОД = d является делителем числа $%42(50n + 9) - 25(84n + 18) = -72$%, к тому же он нечетен (как и первое из чисел).
(30 Ноя '12 19:55)
DocentI
|