Распределение остатка степени

[ProPupil]

Возникла задача, где необходимо работать в кольце вычетов со случайной величиной, а потому немного непонятно как будет выглядеть распределение.

Сама задача выглядит так:

Пусть $p$ - произвольное натуральное число. Пусть $X$ - случайная величина, принимающая значения $0,1,\dots,p-1$ с одинаковой вероятностью. Верно ли, что существует такое число $\varepsilon$, что вероятность того, что $X^{p-1} \equiv 1 \pmod p[math]$[/math], и существует такое простое число $q$, что $q$ делит $p$, и $X^{\frac{p-1}{q}} \equiv 1 \pmod p$, не превосходит $\varepsilon$?

Я знаю, что всего существует $\omega(p-1)$ (A001221) простых делителей числа $p-1$, так что остаётся найти количество тех $q$, что удовлетворяют условию, а вот с этим проблема.

[Brukvalub]

А почему $\varepsilon=1$ не годится, безо всяких там размышлизмов о делителях простых и простых делителях?

[ProPupil]

Потому что число должно быть достаточно малым. (желательно, меньше $1/3$)

[Sonic86]

ProPupil в сообщении #1205170 писал(а):

вероятность того, что $X^{p-1} \equiv 1 \pmod p$

Чего? Последнее соотношение равносильно $X\not\equiv 0 \pmod p$

ProPupil в сообщении #1205170 писал(а):

простое число $q$, что $q$ делит $p$,

Чего? М.б. $q \mid p-1$?

ProPupil в сообщении #1205170 писал(а):

и $X^{\frac{p-1}{q}} \equiv 1 \pmod p$,

Ну а сколько всего таких $X$?

Поставьте задачу нормально плиз
А вообще распределение степеней вроде как достаточно равномерно. Правда я не помню, доказано это или нет.
З.Ы.: topic2164.html - а вот и тема была об этом.

[Батороев]

ProPupil в сообщении #1205170 писал(а):

Пусть $p$ - произвольное натуральное число. Пусть $X$ - случайная величина, принимающая значения $0,1,\dots,p-1$ с одинаковой вероятностью. Верно ли, что существует такое число $\varepsilon$, что вероятность того, что $X^{p-1} \equiv 1 \pmod p[math]$[/math], и существует такое простое число $q$, что $q$ делит $p$, и $X^{\frac{p-1}{q}} \equiv 1 \pmod p$, не превосходит $\varepsilon$?

На мой непросвещенный взгляд, имеется некоторая связь с тестом на простоту Миллера-Рабина.

[MetaMorphy]

Батороев: А на мой взгляд, имеется теснейшая связь с проверкой примитивности элемента $\mathbb{F}_p^{\ast}$ (т.е. того, что он является первообразным корнем $\bmod\ p$).

Автору эта ссылка тоже может быть полезна (после замечаний Sonic86).

[MetaMorphy]

ProPupil: Кстати, а у вас $p$ действительно "произвольное натуральное" (т.е. может не быть простым)?

[Батороев]

MetaMorphy в сообщении #1205734 писал(а):

ProPupil: Кстати, а у вас $p$ действительно "произвольное натуральное" (т.е. может не быть простым)?

Насколько я понял, речь идет о проверке числа $p$ на простоту (т.е. заведомо простота не известна).
Кроме того, по умолчанию со стороны ТС-а, наверное следует считать:

Sonic86 в сообщении #1205227 писал(а):

М.б. $q \mid p-1$?

Далее сообщение del

[Батороев]

После некоторых раздумий появилось подозрение, что задача сводится всего лишь к сопоставлению сравнения $X^{p-1}=X^{\frac{p-1}{q}\cdot {q}}\equiv 1\pmod p$ и числа остатков $X^{q}\pmod p$.
С учетом того, что в задаче требуется найти верхнюю границу $\varepsilon$, по-видимому, следует рассмотреть только простые $p$.