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

[nnosipov]

Да нет, не очевидно: нечётное вполне может делиться на нечётное.

[Батороев]

Я имел в виду необходимую четность степени $2$.

[nnosipov]

Тогда не понял, почему очевидно. Серпинский ссылается на Шинцеля, вряд ли они оба проглядели бы какое-то очевидное рассуждение.

[ИСН]

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

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

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

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

Разве для всех простых $x<p,\;2^x-1\vdots p$? Проверьте на каких-нибудь небольших примерах.

[Батороев]

nnosipov
Выражение $(p_i-1)$ для каждого нечетного простого - четное, соответственно, их НОК тоже будет четным, следовательно, сравнение $2^x-1\equiv0\pmod {y}$, где $x$ - НОК выражений $p_i-1$ всех простых делителей числа $y$ , будет выполняться при четном $x$.

-- 19 дек 2014 19:38 --

Я понял, что не прав.

[timber]

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

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

При рассмотрении $p \mid 2^x-1$ у меня получается такие последовательности (проверял для $x$ до 50):
1)При $p=2$, $x=21, 22, 23, ..., 27$.
2) $p=3$, $x=2, 4, 6, ..., 22, 23, 24, ..., 28$.
3) $p=5$, $x=4, 8, 12, ..., 20, 22, 23, ..., 28$.
4) $p=7$, $x=3, 6, 9, ..., 18, 23, 24, ..., 29$.
5) $p=11$, $x=10, 20, 24, 25, 26, ..., 30, 39, 40, ..., 43$.

Только не понимаю, для чего все это?

[ИСН]

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

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

1)При $p=2$, $x=21, 22, 23, ..., 27$.

Вы действительно это хотели написать, да? Вы уверены? То есть $p=2$ является делителем $2^{21}-1$?

[timber]

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

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

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

1)При $p=2$, $x=21, 22, 23, ..., 27$.

Вы действительно это хотели написать, да? Вы уверены? То есть $p=2$ является делителем $2^{21}-1$?

Я ошибся в программе. Считаю на компьютере. В программе у меня числа округляются вверх.

[ИСН]

Да, разумеется, я так и понял. Ждать исправленного результата?

[timber]

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

Да, разумеется, я так и понял. Ждать исправленного результата?

Да, сейчас исправлю, будет новый результат.

-- 20.12.2014, 14:05 --

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

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

Да, разумеется, я так и понял. Ждать исправленного результата?

Да, сейчас исправлю, будет новый результат.

При рассмотрении $p \mid 2^x-1$ получаются такие последовательности:
1) $p=3$, $x=2, 4, 6, ..., 48, 49, 50$.
2) $p=5$, $x=4, 8, 12, ..., 48, 49, 50$.
3) $p=7$, $x=3, 6, 9, ..., 48, 50$.
4) $p=11$, $x=10, 20, 30, ..., 50$.

В начале получаются арифметические прогрессии. Только вот какое-то странное поведение на концах 48, 49, 50 и 48, 50

Честно говоря я уже запутался. И что нам это дает для понимания того, что, если $2^\delta\equiv 1 \pmod{p}$, то $\delta\mid n$ в доказательстве Шинцеля?

Все-таки очень хотелось бы во всем разобраться. Детально.

[ИСН]

Странное поведение на концах - это опять глюки округления, поверьте уж на слово.
Итак, если $3\mid2^x-1$, то что можно сказать про $x$? (Ну и аналогично для других простых).

[whitefox]

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

Честно говоря я уже запутался. И что нам это дает для понимания того, что, если $2^\delta\equiv 1 \pmod{p}$, то $\delta\mid n$ в доказательстве Шинцеля?

Это, вообще-то, следует из теоремы Лагранжа. Но можете и сами доказать. Для чего нужно $n$ разделить на $\delta$ и посмотреь чему равен остаток.

[nnosipov]

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

Это, вообще-то, следует из теоремы Лагранжа.

Не понимаю, причём здесь Лагранж. Это ведь свойства порядка элемента, почти сразу вытекающее из определения.

[timber]

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

Странное поведение на концах - это опять глюки округления, поверьте уж на слово.
Итак, если $3\mid2^x-1$, то что можно сказать про $x$? (Ну и аналогично для других простых).

Что же сказать про $x$?

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

[whitefox]

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

Не понимаю, причём здесь Лагранж. Это ведь свойства порядка элемента, почти сразу вытекающее из определения.

По теореме Лагранжа $\delta$ делит порядок группы $\varphi(p)=p-1$, так что Лагранж здесь действительно ни причём.

Лучше этим не заморачиваться, и доказать непосредственно, как отмечено выше.