x^n\mod p

[ex-math]

На самом деле, каждое ненулевое значение принимается одинаковое число раз. Чтобы это доказать, воспользуйтесь этим:

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

соотношения $x^n \equiv 1 \pmod{p}$ и $x^d \equiv 1 \pmod{p}$ равносильны.

[megamix62]

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

megamix62 в сообщении #694795 писал(а):

Я так понимаю, $(n,p-1)=d$ равносильно $n=dk$

Опять неправильно понимаете.

Почему ?

Что $n=dk$ ?

[nnosipov]

megamix62 в сообщении #695654 писал(а):

Почему ?

Посмотрите в словаре значение слова "равносильно".

[student]

ex-math в сообщении #695653 писал(а):

Чтобы это доказать, воспользуйтесь этим:
$x^n \equiv 1 \pmod{p}$ и $x^d \equiv 1 \pmod{p}$ равносильны.

Каким образом?

-- Пт мар 15, 2013 19:38:48 --

Пусть $a$ принимает значения из множества $A$, которого мы описали выше.
Так как сравнение $x^n\equiv a\pmod p$ в случае разрешимости имеет ровно $(n,p-1)=d$ решений, следовательно сравнение $x^d\equiv a\pmod p$ тоже имеет ровно $(d,p-1) =d$ решений. Отсюда следует что каждое значение в каждом множестве встречается одинаковое число раз.

Пойдет?