Найдите максимальное возможное значение наибольшего общего делителя чисел 50n+9 и 84n+18, где n — произвольное целое число.

задан 29 Ноя '12 19:28

10|600 символов нужно символов осталось
2

Посмотрите алгоритм Евклида

алгоритм для нахождения наибольшего общего делителя двух целых чисел

Дополнение. По алгоритму Евклида получим, что искомый НОД является делителем 72. Но одно из чисел нечетно, поэтому наибольший НОД равен 9. И это действительно возможно (при n = 0 или 9)

ссылка

отвечен 29 Ноя '12 20:04

изменен 30 Ноя '12 2:03

Можно, конечно, просто умножить первое уравнение на 84, второе - на 50 и вычесть. Получим число (константу), которое делится на НОД. Но это только достаточное условие.
Можно умножить первое уравнение на 42, второе - на 25, эти множители взаимно простые. Но тоже надо доказывать существование подходящего n.

(30 Ноя '12 1:56) DocentI
10|600 символов нужно символов осталось
1

$%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

1

Можно проще. Искомый НОД = d является делителем числа $%42(50n + 9) - 25(84n + 18) = -72$%, к тому же он нечетен (как и первое из чисел).

(30 Ноя '12 19:55) DocentI
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,656
×42

задан
29 Ноя '12 19:28

показан
2630 раз

обновлен
30 Ноя '12 19:55

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru