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

[ИСН]

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

$x$ является членом арифметической прогрессии с шагом $d=p-1$ (для данного примера).

Верно. То самое, что надо. Почти. Только можно сказать конкретнее. А то, знаете, числа 1, 3, 5, 7... тоже являются членами арифметической прогрессии с тем же самым шагом... но есть нюанс.

[timber]

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

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

$x$ является членом арифметической прогрессии с шагом $d=p-1$ (для данного примера).

Верно. То самое, что надо. Почти. Только можно сказать конкретнее. А то, знаете, числа 1, 3, 5, 7... тоже являются членами арифметической прогрессии с тем же самым шагом... но есть нюанс.

Первый член прогрессии $x_1=p-1$ и разность $d=p-1$.

Или нюанс другой?

[ИСН]

Именно такой. А нельзя ли этот смысл выразить покороче, без слов "арифметическая прогрессия"?

[yk2ru]

Само собой, что $n$ - число составное и нечётное. Пусть $n = (n_0+1)n_1$, где $(n_0+1)$ простое число и значит $2^{n_0}$ делит это $(n_0+1)$. А если $2^n$ делит $n$, то оно делит и число $(n_0+1)$.
$(2^n - 1) = (2^{n_0}2^{n_0}...2^{n_0}2^m - 1) = (2^m - 1) \mod (n_0+1)$, где нечётное $m<n_0$ и то, что $2^m - 1$ не делит $(n_0+1)$, думаю что очевидно.

[nnosipov]

yk2ru в сообщении #950013 писал(а):

где нечётное $m<n_0$ и то, что $2^m - 1$ не делит $n_0+1$, думаю что очевидно.

Т.е. $2^3-1$ на $7$ делиться не может?

Кстати, слово "делит" Вы регулярно употребляете в смысле "делится на". (Например, говорят: $3$ делит $6$; это то же самое, что $6$ делится на $3$.)

[yk2ru]

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

делиться не может?

Значит показалось.

[timber]

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

Именно такой. А нельзя ли этот смысл выразить покороче, без слов "арифметическая прогрессия"?

Получается так:
$x_n=x_1+(n-1)d=(p-1)+(n-1)(p-1)=(p-1)n$ $\Rightarrow$ $n\mid x_n

Таким образом, правильно ли я понимаю, что Шинцель в своем доказательстве по аналогии с вышеприведенным, исходя из того, что $2^\delta\equiv 1 \pmod{p}$, сразу делает вывод, что $\delta\mid n$. Но, почему он приводит это без доказательства? Ведь это не так очевидно.

[nnosipov]

$p-1 \mid x_n$ --- вот правильный вывод. То есть, все они делятся на $p-1$.

[timber]

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

$p-1 \mid x_n$ --- вот правильный вывод. То есть, все они делятся на $p-1$.

ну там не для всех $p$ будет $p-1$, например при $p=7$, $x_1=p-4$, соответственно для всех $p$ правильнее будет записать $x_n=(p-n_1)n$

[nnosipov]

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$. Сделайте это.

-- Вс дек 21, 2014 00:54:57 --

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

ну там не для всех $p$ будет $p-1$

Да, не для всех.

[ИСН]

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

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

Вам было очевидно, что $7\times7=49$, до первой собственноручной проверки? Вот и тут то же самое. Если насобачиться - то да, это очевидно.

[timber]

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

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

Именно такой. А нельзя ли этот смысл выразить покороче, без слов "арифметическая прогрессия"?

Получается так:
$x_n=x_1+(n-1)d=(p-1)+(n-1)(p-1)=(p-1)n$ $\Rightarrow$ $n\mid x_n

Таким образом, правильно ли я понимаю, что Шинцель в своем доказательстве по аналогии с вышеприведенным, исходя из того, что $2^\delta\equiv 1 \pmod{p}$, сразу делает вывод, что $\delta\mid n$?

[ИСН]

Да, так.

[timber]

Вариант логики, предлагаемый выше nnosipov - это доказательство другим способом или одно и то же?

[ИСН]

По-моему, одно и то же, но вообще не вникал. Да какая разница. Все правильные доказательства эквивалентны.