Доказать, что для любого натурального n (кроме единицы) 2^n-1 не делится на n

задан 10 Янв '18 13:30

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

Если $%2^n-1$% делится на $%n$%, то $%n$% нечётно. Поскольку $%n > 1$%, число $%n$% имеет простые делители; все они нечётны. Пусть $%p$% -- наименьший из них. Согласно малой теореме Ферма, $%2^{p-1}-1$% делится на $%p$%. Обозначим через $%\nu=\nu(p)$% наименьшее натуральное число, для которого $%2^{\nu}-1$% делится на $%p$% (это порядок элемента $%\bar2\in\mathbb Z_p^{\ast}$% в мультипликативной группе поля).

Из довольно элементарных соображений следует, что $%2^m-1$% делится на $%p$% тогда и только тогда, когда $%m$% делится на $%\nu$%. (Для доказательства достаточно произвести деление $%m$% на $%\nu$% с остатком.) В частности, $%\nu$% делит $%p-1$%. Далее, поскольку $%2^n-1$% делится на $%n$% и на $%p$%, показатель $%n$% также делится на $%\nu$%. Очевидно, что $%\nu > 1$%, то есть это число делится на какое-то простое $%q$%. Получается, что $%n$% делится на $%q$%, где $%q$% делит $%\nu$% и делит $%p-1$%, откуда $%q < p$% -- противоречие с выбором $%p$%.

ссылка

отвечен 10 Янв '18 15:56

@falcao вы говорите, достаточно произвести деление с остатком, получается $$ 2^{m} - 1 = 2^{ \nu \kappa + r} - 1 = 2^{r}( 2^{ \nu \kappa } - 1) + (2^{r} - 1) = 2^{r}( 2^{ \nu} - 1)(2^{ \nu (\kappa - 1)} + \ldots + 1) + (2^{r} - 1) $$ Первое слагаемое действительно делится, а второе нет, почему тогда обязательно $%m = \nu r$%? У вас какие-то другие рассуждения? Мой вопрос в том, достаточность мы доказали, а как доказать необходимость? Пожалуйста не уходите в пространственный ответ.

(13 Май 10:43) Evgeny Kondr...

@Evgeny Kondr...: таких сложных рассуждений тут не надо. Если m=k\nu+r, то 2^m=1 mod p и 2^\nu=1 mod p. Отсюда 2^r=2^m(2^\nu)^{-k}=1 nod p. Остаток r меньше \nu, а оно выбиралось наименьшим натуральным. Значит, r не натуральное, то есть оно равно нулю, и имеет место деление нацело.

Из Вашей формулы всё точно так же следует: 2^r-1 делится на p, и надо воспользоваться тем же условием, что \nu наименьшее. Отсюда r=0, и m=k\nu.

(13 Май 12:33) falcao

@falcao, так и думал( Теория графов Можно, пожалуйста, потревожить вас в последний раз перед экзаменом. Есть идеи по поводу этой задачи? Она висит на форуме давно, но человек, который дал ответ не понял условие.

(13 Май 12:47) Evgeny Kondr...

@Evgeny Kondr...: там есть фраза с любого острова на любой другой можно попасть не более, чем по двум мостам, которая имеет двоякое толкование. Одно такое: два острова не могут быть соединены тремя мостами. Второе: с любого острова на любой можно попасть, ПРОЕХАВ не более чем по двум мостам. Что имели в виду авторы, я не знаю. Задачи с неясным условием обычно решать не хочется.

(13 Май 12:53) falcao

@falcao, они же говорят, по мосту можно ехать в одну сторону, между некоторыми островами есть мосты. И еще добавляют, что либо вы попадаете из одного острова на другой напрямую или через посредника для любой пары островов. Прорешав несколько их экзаменов уже понял что они обычно хотят. Это последняя задача, по которой нет идей.

(13 Май 12:57) Evgeny Kondr...

@Evgeny Kondr...: я помню эту задачу, но там изначально было неправильное толкование из-за небрежной формулировки. Скорее всего, верна именно та трактовка, в которой говорилось в комментарии Романа83. Надо будет прикинуть, что получается при этом. Сейчас я пишу в перерыве между лекциями, и с мыслями собраться некогда. Позже постараюсь подумать.

(13 Май 14:31) falcao

@falcao, спасибо, буду ждать.

(13 Май 14:40) Evgeny Kondr...
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×779

задан
10 Янв '18 13:30

показан
588 раз

обновлен
13 Май 14:40

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

по почте:

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

по RSS:

Ответы

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

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