Доказательство неделимости числа (2^n - 1) на n

[Null]

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

[whitefox]

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

Для нечётных $n:$

1. Допустим $2^n\equiv1\pmod n;$
2. пусть $p$ наименьший простой делитель $n,$ тогда по МТФ $2^{p-1}\equiv1\pmod p;$
3. следовательно . . . что невозможно.

Хинт:

nnosipov в сообщении #947617 писал(а):

Я бы посоветовал из двух делимостей $2^n-1 \vdots p$ и $2^{p-1}-1 \vdots p$ изготовить ещё одну делимость на $p$.

С уточнением: изготовить ещё одну делимость на $q\mid (p-1).$

[nnosipov]

timber в сообщении #947633 писал(а):

Не кажется ли вам, что данная задача слишком сложно решается. Эта задача письменного экзамена (1 час). Причем это задача не в рамках какой-то всероссийской олимпиады по математике школьников или студентов мехматов.

Видите ли, эта задача слишком хорошо известна (возможно, в узких кругах, но тем не менее): см., например, задачу 25 в задачнике Серпинского "250 задач по элементарной теории чисел".

whitefox в сообщении #947645 писал(а):

С уточнением: изготовить ещё одну делимость на $q\mid (p-1).$

Я имел в виду следующее: если $p \mid 2^n-1$ и $p \mid 2^{p-1}-1$, то $p \mid 2^d-1$, где $d=\gcd{(n,p-1)}=1$ (при подходящем выборе $p$). Можно также (как у Серпинского) рассмотреть $\delta$ --- порядок двойки по модулю $p$ (и показать, что $\delta=1$).

[whitefox]

(nnosipov)

А я имел ввиду, что $q\mid \operatorname{ord}_p(2).$

[nnosipov]

(Оффтоп)

whitefox, да, я понял.

[timber]

nnosipov в сообщении #947663 писал(а):

timber в сообщении #947633 писал(а):

Не кажется ли вам, что данная задача слишком сложно решается. Эта задача письменного экзамена (1 час). Причем это задача не в рамках какой-то всероссийской олимпиады по математике школьников или студентов мехматов.

Видите ли, эта задача слишком хорошо известна (возможно, в узких кругах, но тем не менее): см., например, задачу 25 в задачнике Серпинского "250 задач по элементарной теории чисел".

whitefox в сообщении #947645 писал(а):

С уточнением: изготовить ещё одну делимость на $q\mid (p-1).$

Я имел в виду следующее: если $p \mid 2^n-1$ и $p \mid 2^{p-1}-1$, то $p \mid 2^d-1$, где $d=\gcd{(n,p-1)}=1$ (при подходящем выборе $p$). Можно также (как у Серпинского) рассмотреть $\delta$ --- порядок двойки по модулю $p$ (и показать, что $\delta=1$).

Не совсем понятно доказательство Шинцеля в задачнике Серпинского:
1) Почему, если $2^\delta\equiv 1 \pmod{p}$, делается вывод, что $\delta\mid n$.
2) Почему делается итоговый вывод: число $n$ имеет делитель $>1$ и $<p$, а значит, также и простой делитель с этим свойством, что противоречит определению числа $p$. Правильно ли я понимаю это так: $1 <\delta <p$, в свою очередь число $\delta$ должно делится на какое-то простое число, допустим $p_2$, но $p_2 < p$ не может быть, так как $p$ - наименьшее?

[Deggial]

timber в сообщении #949382 писал(а):

$2^\delta\equiv1$ (mod p)

timber, замечание за неправильное оформление формул.
$a\equiv b \pmod{m}$.

[ИСН]

2) Да, так.
1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.

[Cash]

ИСН в сообщении #949392 писал(а):

1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.

Я бы задал вопрос более конкретно.
Если $\delta$ -порядок двойки по модулю $p$, то докажите, что $2^x\equiv 1 \pmod{p} \Leftrightarrow \delta\mid x$

[timber]

Цитата:

1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.

Для всех простых степеней двойки $x\in N_p.

[ИСН]

Что такое $N_p$?

[timber]

ИСН в сообщении #949410 писал(а):

Что такое $N_p$?

Подмножество простых чисел множества натуральных чисел.

[ИСН]

Разве для всех простых $x$ у нас $2^x-1$ делится на $p$?

[timber]

ИСН в сообщении #949416 писал(а):

Разве для всех простых $x$ у нас $2^x-1$ делится на $p$?

при условии $x < p$

[Батороев]

whitefox в сообщении #947618 писал(а):

Для четного $n$ доказательство очевидно.

Для нечетного, с учетом необходимой четности степени двойки, на мой взгляд, тоже очевидно. Или я ошибаюсь?