2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3
 
 Re: x^n\mod p
Сообщение14.03.2013, 18:59 
Аватара пользователя
На самом деле, каждое ненулевое значение принимается одинаковое число раз. Чтобы это доказать, воспользуйтесь этим:
nnosipov в сообщении #694084 писал(а):
соотношения $x^n \equiv 1 \pmod{p}$ и $x^d \equiv 1 \pmod{p}$ равносильны.

 
 
 
 Re: x^n\mod p
Сообщение14.03.2013, 19:00 
nnosipov в сообщении #694897 писал(а):
megamix62 в сообщении #694795 писал(а):
Я так понимаю, $(n,p-1)=d$ равносильно $n=dk$
Опять неправильно понимаете.

Почему ?

Что $n=dk$ ? :twisted:

 
 
 
 Re: x^n\mod p
Сообщение14.03.2013, 19:09 
megamix62 в сообщении #695654 писал(а):
Почему ?
Посмотрите в словаре значение слова "равносильно".

 
 
 
 Re: x^n\mod p
Сообщение15.03.2013, 17:20 
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$ решений. Отсюда следует что каждое значение в каждом множестве встречается одинаковое число раз.

Пойдет?

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


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