Какое наибольшее значение может быть у наибольшего общего делителя чисел 13n + 6 и 17n + 1, если n — натуральное число?--- разбирала задачу на примере:

"НОД(11n+6,23n+5)=НОД(11n+6,n-7)=НОД(83,n-7)

Первое равенство следует из 23n+5-2(11n+6)=n-7; второе из 11n+6-11(n-7)=83.

При n=7 достигается наибольшее значение, равное 83." и не совсем поняла почему "=НОД(11n+6,n-7)=НОД(83,n-7)" помогите пожалуйста!

задан 4 Янв '14 23:45

изменен 17 Янв '14 20:32

Deleted's gravatar image


126

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

Когда есть конкретные вопросы по решению, это всегда хорошо.

При n=7 получается НОД(83,n-7), где второе число обращается в ноль. Чему равен НОД чисел 83 и 0? Очевидно, он равен 83, так как и 83, и 0 делятся на 83. То есть это общий делитель. Он будет наибольшим, потому что 83 не делится ни на какое большее число.

При желании, можно просто подставить n=7 в исходные формулы и непосредственно убедиться в том, что получатся два числа, у которых НОД именно такой.

Теперь ответ на второй вопрос. Используется такой общий принцип: НОД(a,b) всегда равен НОД(a-b,b). Доказательство простое: у чисел a;b общие делители те же, что и у чисел a-b;b. Ведь если a и b оба на что-то делятся, то на это же число делится и разность. И обратно: если a-b и b на что-то делятся, то их сумма, равная a, делится на то же число.

Этот принцип можно применять многократно, и тогда получится, что НОД(a,b)=НОД(a-b,b)=НОД(a-2b,b)=НОД(a-3b,b)=..., и так столько раз, сколько мы сочтём нужным. Здесь одно число не меняется, а из другого оно вычитается один раз или несколько.

Теперь рассмотрим ситуацию НОД(11n+6,n-7). Мы число n-7 не меняем, а из первого числа, равного 11n+6, вычитаем второе 11 раз подряд. Тогда вместо 11n+6 появится разность 11n+6-11(n-7), равная 6+11*7=6+77=83, как и утверждалось. При таких операциях НОД не меняется, то есть он был таким же, как и НОД(83,n-7).

ссылка

отвечен 5 Янв '14 0:33

Для (13n + 6) и (17n + 1); (17n + 1) - (13n + 6) = 4n - 5; (17n + 1) - 4(4n - 5) = n + 21; n = - 21. А что дальше делать? Не может, наверное, НОД быть отрицательным числом? Принцип понятен, а полученный результат зовёт на консультацию.

(5 Янв '14 1:43) nikolaykruzh...

@nikolaykruzh...: Вы рано остановили процесс. Там нужен ещё один шаг. На данный момент есть два числа: 4n-5 и n+21. Надо из первого вычесть второе 4 раза, и получится константа. Положительна она или отрицательна -- не важно. Дело в том, что мы ищем наибольшее натуральное число с определённым свойством. Например, НОД(12;18)=6. Но надо иметь в виду, что знаки чисел под знаком НОД никак не влияют. Например, НОД(-12;18) также равно 6, по определению. Это наибольшее натуральное число, на которое делятся -12 и 18. То есть знака минус бояться не надо.

(5 Янв '14 2:04) falcao

Хорошо, что Вы у нас есть,@falcao! Спасибо!

(5 Янв '14 16:02) nikolaykruzh...

Почему идёт дамножение на 4 (17n+1)-4(4n-5)

(17 Янв '14 17:21) linilo35

@linilo35: в тот момент, когда у нас есть числа 17n+1 и 4n-5 мы действуем следующим образом. Делим больший из коэффициентов при n (то есть 17) на меньший (на 4). Получается частное q=4 и остаток r=1. Это значит, что нам выгодно вычесть из первого числа второе число, умноженное на q, так как коэффициент при n у разности станет равным r и тем самым уменьшится.

Вообще, эта задача имеет в своей основе некое обобщение классического алгоритма Евклида, с которым полезно было бы ознакомится до решения самой задачи.

(17 Янв '14 17:35) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,706
×530
×58

задан
4 Янв '14 23:45

показан
3558 раз

обновлен
17 Янв '14 17:35

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

по почте:

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

по RSS:

Ответы

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

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