Малая теорема Ферма

[dreamkiller]

Малая теорема Ферма гласит, что $a^{p-1} \equiv 1 (\mod p)$ для простого р.
Можно ли каким-то образом описать множество тех чисел, для которых $a^{n-1} \equiv 1 (\mod p) $ может выполниться только для $n \geq p$?

[xmaister]

dreamkiller в сообщении #634479 писал(а):

Можно ли каким-то образом описать множество тех чисел, для которых $a^{n-1} \equiv 1 (\mod p) $ может выполниться только для $n \geq p$?

Полностью такое множество описать вряд ли можно, хотя могу и ошибаться. Для этого надо найти порядок элемента $a\in\mathbb{F}_p^{\times}$.

[venco]

dreamkiller в сообщении #634479 писал(а):

Малая теорема Ферма гласит, что $a^{p-1} \equiv 1 (\mod p)$ для простого р.
Можно ли каким-то образом описать множество тех чисел, для которых $a^{n-1} \equiv 1 (\mod p) $ может выполниться только для $n \geq p$?

$n>p$ быть не может. А равенство достигается для простых и псевдопростых по основанию $a$.

[xmaister]

venco в сообщении #634495 писал(а):

$n>p$ быть не может.

Как это? $n=2p-1$ не подходит?

[AV_77]

xmaister в сообщении #634498 писал(а):

Как это? $n=2p-1$ не подходит?

Нет, вопрос в другом заключался:

dreamkiller в сообщении #634479 писал(а):

Можно ли каким-то образом описать множество тех чисел, для которых $a^{n-1} \equiv 1 \pmod{p}$ может выполниться только для $n > p$?

[venco]

xmaister в сообщении #634498 писал(а):

venco в сообщении #634495 писал(а):

$n>p$ быть не может.

Как это? $n=2p-1$ не подходит?

Требуется, чтобы равенство выполнялось только для $n\ge p$. А оно будет выполняться ещё для $n \bmod \phi(p) < p$.

[dreamkiller]

Имеется ввиду то, что ни для какого $n < p$ мы не получим равенство. Разумеется, что при $n = p $ оно выполнится.

[venco]

Тогда $n=p$ только для простых $p$ и некоторых $a$. В остальных случаях $n<p$.

[dreamkiller]

venco в сообщении #634515 писал(а):

Тогда $n=p$ только для простых $p$ и некоторых $a$. В остальных случаях $n<p$.

Задача в том, можно ли как-то описать по-простому множество всех а.

[venco]

Зависит от того, что вы понимаете под "по простому".
А так вам нужен primitive root, количество которых равно $\phi(\phi(p))$, или $\phi(p-1)$ для простого $p$. Найти их всех - нетривиальная задача.

[dreamkiller]

venco в сообщении #634547 писал(а):

Зависит от того, что вы понимаете под "по простому".
А так вам нужен primitive root, количество которых равно $\phi(\phi(p))$, или $\phi(p-1)$ для простого $p$. Найти их всех - нетривиальная задача.

Спасибо за ссылку. Вопрос можно считать решенным. Способ их нахождения описан на википедии

[vasili]

Существует ли такое простое число $P$, что$2^P- 1\equiv1\pmod {P^2}$?

[Sonic86]

vasili в сообщении #643888 писал(а):

Существует ли такое простое число $P$, что$2^P- 1\equiv1\pmod {P^2}$?

Да, $1089$ и $1093$ например. Гуглите "простые Вивериха", "Wieferich prime"
http://en.wikipedia.org/wiki/Wieferich_prime
А тему с новым вопросом надо создавать свою.