2014 dxdy logo

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

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




 
 Первообразные корни и вычеты
Сообщение10.09.2006, 19:55 
Аватара пользователя
Докажите, что первообразный корень по простому модулю $p\not =2$ не может быть квадратичным вычетом.

 
 
 
 
Сообщение10.09.2006, 21:51 
Аватара пользователя
Если первообразный корень $a$ является кв.вычетом, то $a^{(p-1)/2}\equiv 1\pmod p$, но тогда он не может порождать все ненулевые вычеты по модулю $p$, т.е. быть первообразным корнем.

 
 
 
 
Сообщение11.09.2006, 06:14 
Аватара пользователя
Да, вопрос был очень простой. В рамках этого вопроса следующий того же плана:
доказать, что для первообразного корня $a$ имеем $a^{\frac{p(p-1)}{2}}=-1\mod{p}$.

 
 
 
 
Сообщение11.09.2006, 06:40 
Аватара пользователя
Артамонов Ю.Н. писал(а):
доказать, что для первообразного корня $a$ имеем $a^{\frac{p(p-1)}{2}}=-1\mod{p}$.

Для первообразного корня имеем $a^{\frac{p-1}{2}}\equiv -1\pmod{p}$. Возводим это сравнение в степень $p$ и получаем требуемое.

 
 
 
 
Сообщение11.09.2006, 07:00 
Аватара пользователя
Можно еще так: $\prod\limits_{i=1}^{p-1}a^i\equiv(p-1)!\mod{p}$, или по теореме Вильсона $\prod\limits_{i=1}^{p-1}a^i\equiv -1\mod{p}$, или $a^{\frac{p(p-1)}{2}}\equiv -1 \mod{p}$.

 
 
 
 
Сообщение11.09.2006, 14:33 
Аватара пользователя
Честно говоря, меня в этой теме интересует вопрос - можно ли для заданного $p$ сказать, сколько будет первообразных корней, т.е. найти критерии выделения их из множества квадратичных невычетов.

 
 
 
 
Сообщение11.09.2006, 14:44 
Аватара пользователя
Артамонов Ю.Н. писал(а):
можно ли для заданного $p$ сказать, сколько будет первообразных корней,

Первообразных корней по модулю простого $p$ ровно $\varphi(p-1)$, где $\varphi$ - функция Эйлера.
Артамонов Ю.Н. писал(а):
т.е. найти критерии выделения их из множества квадратичных невычетов.

Число $a$ является первообразным корнем по модулю $p$ тогда и только тогда, когда для каждого простого делителя $q$ числа $p-1$ выполняется $a^{(p-1)/q} \not\equiv 1\pmod p.$

Кроме того, если известен один первообразный корень $a,$ то все остальные первообразные корни получаются как $a^k\bmod p,$ где $1<k<p-1$ и $(k,p-1)=1.$

 
 
 
 
Сообщение11.09.2006, 19:01 
Аватара пользователя
Спасибо!

 
 
 [ Сообщений: 8 ] 


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