Первообразные корни и вычеты

[juna]

Докажите, что первообразный корень по простому модулю $p\not =2$ не может быть квадратичным вычетом.

[maxal]

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

[juna]

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

[maxal]

Артамонов Ю.Н. писал(а):

доказать, что для первообразного корня $a$ имеем $a^{\frac{p(p-1)}{2}}=-1\mod{p}$.

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

[juna]

Можно еще так: $\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}$.

[juna]

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

[maxal]

Артамонов Ю.Н. писал(а):

можно ли для заданного $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.$

[juna]

Спасибо!