Сравнение по модулю - правильно ли решаю

[artempalkin]

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

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

Подозреваю, что как-то так можно и вывести теорему Эйлера как обобщение малой теоремы Ферма. Но вообще сегодня я впервые в жизни узнал, как они обе доказываются, и поработал со сравнениями по модулю. Интересная штука.

[nnosipov]

artempalkin в сообщении #1445477 писал(а):

Подозреваю, что как-то так можно и вывести теорему Эйлера как обобщение малой теоремы Ферма.

Правильно подозреваете. Рекомендую когда-нибудь сделать это упражнение. В качестве бонуса можно будет усилить теорему Эйлера до теоремы Кармайкла (вместо функции Эйлера в сравнении будет фигурировать функция Кармайкла).

[artempalkin]

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

В качестве бонуса можно будет усилить теорему Эйлера до теоремы Кармайкла

Спасибо, что верите в меня :) Когда-нибудь проделаю это обязательно.

[Andrey A]

На всякий случай $5^\frac{p(p-1)}{2} \equiv -1 \mod p^2$ для простых $p>5$ вида $4k+1$. Это не обязательно наименьший показатель, но кратный наименьшему: $5^{26}+1=2 \cdot 13^2 \cdot 53 \cdot 83181652304609.$

[nnosipov]

Andrey A в сообщении #1445506 писал(а):

На всякий случай $5^\frac{p(p-1)}{2} \equiv -1 \mod p^2$ для простых $p>5$ вида $4k+1$.

Нет, это неправда. Указанное сравнение верно для нечетных простых $p \equiv \pm 2 \pmod{5}$ (потому, что символ Лежандра $(5/p)=-1$ для таких $p$).

[Andrey A]

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

... для нечетных простых $p \equiv \pm 2 \pmod{5}$

Да, Вы правы. Неточно выразился, имелось в виду следующее: для простых $p=4k+1$ наименьший показатель (корень сравнения $5^x \equiv -1 \mod p^2$) делит $\dfrac{p(p-1)}{2}.$

[nnosipov]

Andrey A в сообщении #1445594 писал(а):

имелось в виду следующее: для простых $p=4k+1$ наименьший показатель (корень сравнения $5^x \equiv -1 \mod p^2$) делит $\dfrac{p(p-1)}{2}.$

Непонятно, почему Вы это свойство связываете именно с простыми $p=4k+1$. Оно имеет место для любых простых чисел $p \neq 5$. Другое дело, что не для всех $p$ сравнение $5^x \equiv -1 \pmod{p^2}$ разрешимо. Но и здесь простые $p=4k+1$ ни при чем: это сравнение может быть для них как разрешимым, так и неразрешимым.

[Andrey A]

nnosipov
Да, для $p=101,109$ неразрешимо. То есть разрешимо, но не по основанию $5$. Моя ошибка. Спасибо.