x^n\mod p

[student]

Пусть $p$- простое число, $n$-натуральное число и $(n,p-1)=d$.
Докажите, что если $x$ пробегает полную систему вычетов по модулю $p$ то множества чисел вида $x^n\mod p$ является перестановкой множества чисел вида $x^d\mod p$.

[Sonic86]

Как пытались решать?
Попробуйте использовать цикличность группы $\mathbb{Z}_{p}^{\times}$.

[xmaister]

Достаточно воспользовать определнием НОД и вспомнить малую теорему Ферма.

[student]

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

Как пытались решать?
Попробуйте использовать цикличность группы $\mathbb{Z}_{p}^{\times}$.

Понятно что сравнение $x^{n}\equiv y^d \mod p$ относительно $y$ при любом фиксированном $x$ всегда имеет решение.( В качестве $y$ можно взять $x^{n/d}\mod p$).
А вот откуда мы знаем, что данное сравнение относительно $x$ при любом фиксированном $y$ всегда имеет решение?

-- Пн мар 11, 2013 08:20:01 --

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

Достаточно воспользовать определнием НОД и вспомнить малую теорему Ферма.

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

[xmaister]

Не получается прям так в лоб, не досмотрел.

[nnosipov]

Да всё там получается. Достаточно понять, что соотношения $x^n \equiv 1 \pmod{p}$ и $x^d \equiv 1 \pmod{p}$ равносильны. Вообще, группа $Z_p^*$ здесь не причём, вместо неё можно взять любую конечную абелеву группу (но, понятно, вместо малой теоремы Ферма нужна будет теорема Лагранжа).

[student]

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

Да всё там получается. Достаточно понять, что соотношения $x^n \equiv 1 \pmod{p}$ и $x^d \equiv 1 \pmod{p}$ равносильны.

А как отсюда можно доказать что, $x^n \equiv a \pmod{p}$ и $x^d \equiv a \pmod{p}$ при $a\ne 1$ тоже равносильны?

[nnosipov]

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

А как отсюда можно доказать что, $x^n \equiv a \pmod{p}$ и $x^d \equiv a \pmod{p}$ при $a\ne 1$ тоже равносильны?

Никак. Они не равносильны.

Вспомните, что именно Вам нужно доказать. И именно это и доказывайте.

[student]

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

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

А как отсюда можно доказать что, $x^n \equiv a \pmod{p}$ и $x^d \equiv a \pmod{p}$ при $a\ne 1$ тоже равносильны?

Никак. Они не равносильны.

Вспомните, что именно Вам нужно доказать. И именно это и доказывайте.

Тогда как доказывать? Что то не понимаю.....

[nnosipov]

Рассмотрим, к примеру, отображение $\phi_1:Z_p^* \to Z_p^*$, заданное формулой $\phi_1(x)=x^d$. Слово "гомоморфизм" о чём-нибудь говорит? (И без него можно обойтись, но с ним быстрее.)

[megamix62]

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

Пусть $p$- простое число, $n$-натуральное число и $(n,p-1)=d$.
Докажите, что если $x$ пробегает полную систему вычетов по модулю $p$ то множества чисел вида $x^n\mod p$ является перестановкой множества чисел вида $x^d\mod p$.

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

Исправил

[nnosipov]

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

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

Неправильно понимаете. Здесь $(n,p-1)$ обозначает НОД чисел $n$ и $p-1$.

[student]

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

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

Тоже неправильно!

[student]

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

Рассмотрим, к примеру, отображение $\phi_1:Z_p^* \to Z_p^*$, заданное формулой $\phi_1(x)=x^d$. Слово "гомоморфизм" о чём-нибудь говорит? (И без него можно обойтись, но с ним быстрее.)

Не понятно. А можно доказать чисто на языке теории чисел?

[nnosipov]

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