Интересно: сколько максимально существует взаимно простых натуральных чисел, которые есть последовательными членами арифметической прогрессии и меньше 1000?

задан 4 Авг '16 18:24

1

Вы имеете в виду, что члены прогрессии должны быть взаимно просты попарно?

(4 Авг '16 19:45) falcao
1

Да. Все члены арифметической прогрессии должны быть взаимно простыми натуральными числами.

(4 Авг '16 19:57) katerina
10|600 символов нужно символов осталось
1

Рассмотрим прогресиию из 13 членов с разностью 30, а именно, 331, 361, 391, ... , 691. Проверим, что все числа в ней попарно взаимно просты. Если это не так, то разность двух чисел делится на некоторое простое p. Очевидно, что p не равно 2, 3 или 5, так как это делители числа 30, а первое число сравнимо с 1 по модулю 30. Разность двух чисел имеет вид 30k, где k не превышает 12. Получается, что k делится на p, откуда p=7 или p=11. Нетрудно проверить, что посередине прогрессии находится число число 511, делящееся на 7. Предыдущее и следующее числа с этим свойством -- это 301 и 721 (через 7 шагов влево и вправо); они в последовательность не входят. На 11 делится пятый член прогрессии, число 451. Следующий член с этим свойством должен быть 16-м, и его в последовательности нет. То же касается предыдущего. Таким образом, все числа прогрессии попарно взаимно просты.

Докажем, что более длинных прогрессий с требуемым свойством не имеется. Допустим, что длина прогрессии не меньше 14. Тогда разность прогрессии не больше 76 (поделили 999 на 13 с остатком). Тем самым, разность прогрессии не может делиться сразу на 2, 3, 5, 7. Если она не делится на p, где p<=7, то остатки от деления на p периодически повторяются ровно через p шагов, и среди чисел периода встречаются по разу все остатки, включая 0. Значит, при длине >=14>=2p остаток 0 встретится дважды, и два члена прогрессии окажутся не взаимно простыми.

ссылка

отвечен 7 Авг '16 14:55

Спасибо! Скажите, пожалуйста, а почему первый член прогрессии берем именно 331, а не, к примеру, 23?

(7 Авг '16 15:42) katerina

@katerina: здесь есть несколько ограничений, поэтому мы сначала за основу можем брать 1, а потом сдвигать как нам удобно. Из анализа ясно, что длину 13 мы можем получить только если средний член делится на 7. Тогда это 301 с периодом 210. Если начать со 121, чтобы посередине было 301, то по модулю 11 два остатка будут нулевыми. А если прибавить 210 ко всем числам, то все свойства будут выполнены. Важно, чтобы остаток 0 от деления на 11 не располагался слишком близко к краю, поэтому 121 в качестве первого числа не годится.

Но 23 тоже брать можно -- там все свойства выполнены.

(7 Авг '16 16:52) falcao

Спасибо!!!

(7 Авг '16 19:10) katerina
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×205
×9

задан
4 Авг '16 18:24

показан
400 раз

обновлен
7 Авг '16 19:10

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

по почте:

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

по RSS:

Ответы

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

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