2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: x^n\mod p
Сообщение10.03.2013, 20:51 
Как пытались решать?
Попробуйте использовать цикличность группы $\mathbb{Z}_{p}^{\times}$.

 
 
 
 Re: x^n\mod p
Сообщение10.03.2013, 22:25 
Аватара пользователя
Достаточно воспользовать определнием НОД и вспомнить малую теорему Ферма.

 
 
 
 Re: x^n\mod p
Сообщение11.03.2013, 06:19 
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 писал(а):
Достаточно воспользовать определнием НОД и вспомнить малую теорему Ферма.

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

 
 
 
 Re: x^n\mod p
Сообщение11.03.2013, 10:21 
Аватара пользователя
Не получается прям так в лоб, не досмотрел.

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

 
 
 
 Re: x^n\mod p
Сообщение12.03.2013, 07:07 
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$ тоже равносильны?

 
 
 
 Re: x^n\mod p
Сообщение12.03.2013, 07:48 
student в сообщении #694382 писал(а):
А как отсюда можно доказать что, $x^n \equiv a \pmod{p}$ и $x^d \equiv a \pmod{p}$ при $a\ne 1$ тоже равносильны?
Никак. Они не равносильны.

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

 
 
 
 Re: x^n\mod p
Сообщение12.03.2013, 10:21 
nnosipov в сообщении #694386 писал(а):
student в сообщении #694382 писал(а):
А как отсюда можно доказать что, $x^n \equiv a \pmod{p}$ и $x^d \equiv a \pmod{p}$ при $a\ne 1$ тоже равносильны?
Никак. Они не равносильны.

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

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

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

 
 
 
 Re: x^n\mod p
Сообщение12.03.2013, 15:21 
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$

Исправил

 
 
 
 Re: x^n\mod p
Сообщение12.03.2013, 15:24 
megamix62 в сообщении #694521 писал(а):
Я так понимаю, $(n,p-1)=d$ равносильно $n=d(p-1)$
Неправильно понимаете. Здесь $(n,p-1)$ обозначает НОД чисел $n$ и $p-1$.

 
 
 
 Re: x^n\mod p
Сообщение12.03.2013, 18:36 
megamix62 в сообщении #694521 писал(а):
Я так понимаю, $(n,p-1)=d$ равносильно $n=d+k(p-1)$
Исправил

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

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

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

 
 
 
 Re: x^n\mod p
Сообщение12.03.2013, 19:59 
Нет здесь никакой теории чисел, здесь теория групп. Но если всё-таки хочется теории чисел, то нужно знать, что такое "первообразный корень по модулю $p$". Знаете,что это такое?

 
 
 [ Сообщений: 34 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group