x^n\mod p

[student]

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

Нет здесь никакой теории чисел, здесь теория групп. Но если всё-таки хочется теории чисел, то нужно знать, что такое "первообразный корень по модулю $p$". Знаете,что это такое?

Да.

[nnosipov]

В каком виде можно представить любой $x \in Z_p^*$, если известен некоторый первообразный корень $g$ по модулю $p$?

[student]

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

В каком виде можно представить любой $x \in Z_p^*$, если известен некоторый первообразный корень $g$ по модулю $p$?

$g^k\mod p$, где $1\le k\le p-1$.

[RIP]

(Оффтоп)

Можно же и без первообразных корней. Достаточно НОД представить в виде $d=an+b(p-1)$. Работает для любой конечной группы.

[student]

RIP в сообщении #694779 писал(а):

Достаточно НОД представить в виде $d=an+b(p-1)$. Работает для любой конечной группы.

Откуда мы знаем, что при возведение в степен $a$ множество чисел вида $x^n$ не сужается?

[megamix62]

Я так понимаю, $(n,p-1)=d$ равносильно $n=dk$ , тогда
$x^n=x^{dk}=(x^{d})^k\mod p$

У Grehem_r_knut_d_patashnik "Konkretnaya_matematika" стр.154 что-то похожее...

[student]

1. Пусть $A=\{x^n \mod p, 1\leq x\leq p-1\}$ и $B=\{x^d \mod p, 1\leq x\leq p-1\}.$
2. Так как $x^{n}\equiv (x^{n/d})^d\mod p$, поэтому $A\subset B$.
3. Если $x$ пробегает приведенную систему вычетов по модулю $p$ то $x^{-1} \mod p$ тоже пробегает проведенную систему вычетов по модулю $p$, следовательно множества чисел вида $x^{a}$ и множества чисел вида $x^{-a}$ отличаются друг от друга только перестановками.
4. $d=(n,p-1)\Rightarrow d=a\cdot n+b\cdot(p-1)\Rightarrow x^d\mod p=(x^a)^n\mod p\Rightarrow B\subset A$.
5. Следовательно A=B.

Можно ли считать это доказательством?

[nnosipov]

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

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

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

student в сообщении #694813 писал(а):

Можно ли считать это доказательством?

Да, но это опять теория групп. А Вы хотели только теорию чисел. Попробуйте получить равенство $A=B$, опираясь на представление $x \equiv g^k \pmod{p}$, где $g$ --- первообразный корень по модулю $p$.

[ex-math]

Разве малая теорема Ферма, линейное представление НОД и свойства сравнений -- это теория групп?

Кстати, доказательство не полно. ТС пока доказал, что множества значений $x^n$ и $x^d$ совпадают. Еще нужно проверить, что каждое значение принимается $x^n$ и $x^d$ одинаковое число раз.

[nnosipov]

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

Разве малая теорема Ферма, линейное представление НОД и свойства сравнений -- это теория групп?

Ну, малая теорема Ферма --- это точно теория групп, остальное можно отнести к теории колец. Вообще, сама задача ТС --- это упражнение по теории групп, которое использует совершенно стандартные теоретико-групповые конструкции. Можно, конечно, их не замечать, но лучше всё-таки о них знать.

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

Кстати, доказательство не полно. ТС пока доказал, что множества значений $x^n$ и $x^d$ совпадают. Еще нужно проверить, что каждое значение принимается $x^n$ и $x^d$ одинаковое число раз.

По-моему, этого не требуется в задаче. Но если нужен и этот факт, то я за то, чтобы выучить слово "гомоморфизм". Это всего лишь элементарная алгебраическая грамотность.

[ex-math]

Если на то пошло, то $g^k$ -- это тоже теория групп, и тоже гомоморфизм.

Как я понял, ТС хочет решить эту задачу, не привлекая алгебраических конструкций, реализацию которых являют собой целые числа.

Да, а в условии речь идет о том, что $x^n$ являются перестановками $x^d$.

[nnosipov]

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

Если на то пошло, то $g^k$ -- это тоже теория групп, и тоже гомоморфизм.

Ну да, и это тоже. Но тут хотя бы простота числа $p$ используется.

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

ТС хочет решить эту задачу, не привлекая алгебраических конструкций

Встреча с ними неизбежна, чего тянуть.

[student]

Вообще-то, я это взял из книги Коробова "Тригонометрические суммы и их приложения", но что то там это очевидная вещь.

[ex-math]

Ну Коробов как бы предполагал, что если читатель начал изучать аналитическую теорию чисел, то элементарную он уже освоил.

[student]

ex-math
А как можно доказать, что элементы в каждое из этих множеств встречаются одинаковое количество раз?