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

[timber]

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

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

Ведь это не так очевидно.

Это почти очевидно. Вот смотрите: $\delta$ --- это самое маленькое число, такое, что $2^\delta \equiv 1 \pmod{p}$. А $n$ --- это какое-то число, для которого $2^n \equiv 1 \pmod{p}$. Нужно увидеть, что $n$ кратно $\delta$. Для этого поделим $n$ на $\delta$ с остатком: $n=\delta q+r$, где $0 \leqslant r<\delta$. Осталось показать, что $r=0$. Сделайте это.

Ну может быть так:
1) допустим, что $r>0$ и тогда $2^n-1=2^{\delta q+r}-1=2^{\delta q+r}-2^r+2^r-1=2^r(2^{\delta q}-1)+(2^r-1)$ или $2^r-1=(2^n-1)-2^r(2^{\delta q}-1)$.
2) Так как $(2^n-1)\vdots p$ и (2^{\delta q}-1)\vdots p$, то правая часть тождества из пункта 1) делится на $p$, соответственно и левая часть $(2^r-1)\vdots p$, но этого не может быть, так как $0<r<\delta$ и $\delta$ - это наименьшее число для которого $(2^\delta-1)\vdots p$.
3) Следовательно противоречие и $r=0$.

Так?

[nnosipov]

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

Так?

Да, именно так.

[timber]

Друзья, большое спасибо всем за помощь!

Особо благодарю участников ИСН и nnosipov, которые своими чуткими намеками помогли мне более-менее понять доказательство Шинцеля.

Но, вот все-таки это доказательство не простое. И как-то сомнительно, чтобы оно являлось ответом на вступительном экзамене в компьютерную школу.

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

[ИСН]

Если знать теорему Ферма настолько, чтобы она являлась как бы продолжением рук (как лыжи у чукчи - продолжение ног), то это просто и элементарно. По-другому, может, и можно, но проще не будет.

[timber]

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

Если знать теорему Ферма настолько, чтобы она являлась как бы продолжением рук (как лыжи у чукчи - продолжение ног), то это просто и элементарно. По-другому, может, и можно, но проще не будет.

Вы можете посоветовать хорошую уникальную литературу на эту тему?

[ИСН]

Я могу посоветовать перестать искать хорошую уникальную литературу на эту, а равно и на любую другую тему. Хорошей уникальной литературы не бывает и не может быть. Чтобы узнать факты, годится любая литература. А чтобы научиться ими пользоваться, надо ими пользоваться, другого способа нет. Никакая литература этого за Вас не сделает.

[rightways]

А вот нат. чисел $n$ для которых $n|2(2^n-1)$ - бесконечно.

[nnosipov]

rightways в сообщении #967867 писал(а):

А вот нат. чисел $n$ для которых $n|2(2^n-1)$ - бесконечно.

Да, удвоенные степени тройки подходят, например.

[bazalt]

Прочитал дважды данную тему но так и не понял ключевого момента в доказательстве.

Почему $(2^{\delta q}-1)\vdots p$?

[Lia]

bazalt
Все обозначения из Вашего поста раскиданы по теме. Тема четырехлетней давности и уже никто ничего не помнит, которое из них за что отвечало, да и участники могут отсутствовать. Поэтому будет целесообразно сделать пост удобным для прочтения, сформулировав все в одном месте. Сделайте, пожалуйста.

[maxal]

Обобщение:
Докажите, что не существует последовательности целых чисел $n_1,n_2,\dots,n_k$ больших 1 такой, что $n_1\mid 2^{n_2}-1$, $n_2\mid 2^{n_3}-1$, ..., $n_{k-1}\mid 2^{n_k}-1$, $n_k\mid 2^{n_1}-1$.

[SiberianSemion]

По поводу задачи постом выше.

При доказательстве можно исходить из того, что наименьшие простые делители заданных чисел увеличиваются. Формально определим транзитивное отношение $a\,R\,b$ $-$ "наименьший простой делитель $a$ больше наименьшего простого делителя $b$." Используя идею исходной задачи из темы, легко доказать, что $n_1\,R\,n_2, n_2\,R\,n_3, \ldots, n_k\,R\,n_1,$ откуда $n_1\,R\,n_1,$ противоречие.

[vatrushka]

Извиняюсь за некропостинг, но сегодня разбираясь в этой задаче, понял что ее можно решить чуть чуть проще и понятнее
А именно: имеется такой факт $GCD(a^n - 1, a ^ m - 1) = a ^ {(GCD(n, m))} - 1$. (задача 3.66 из Алфутова, Теория чисел)
Далее, аналогично доказываем для четного, для простого нечетного по МФТ, а для составного нечетного:
Пусть это выполняется для некоторого $n$
Пусть $p$ - наименьший простой делитель $n$
По МТФ $2^{(p - 1)} - 1$ делиться на $p$.
По предположению $2^n - 1$ делиться на $n$, а значит и на $p$ т.к. $p$ - делитель $n$.
Далее $GCD(2^{p - 1} - 1, 2 ^n - 1) = 2 ^ {GCD(p - 1, n)} - 1$
Т.к. $p$ - наименьший простой делитель $n$, $p - 1$ и $n$ - взаимно просты, а значит $GCD(p-1, n) = 1$, значит
$GCD(2^{p - 1} - 1, 2 ^n - 1) = 2^1 - 1 = 1$, значит они взаимнопросты, но по предположению $2^n - 1$ делиться на $n$, а значит и на $p$,
По МТФ $2^{(p - 1)} - 1$ делиться на $p$, значит их $GCD$ не может быть равен единице
Противоречие.

[nnosipov]

vatrushka
Я об этом (как одном из способов решения) писал здесь http://dxdy.ru/post947663.html#p947663