Критерий Эйлера

[Ward]

Всем привет!
Помогите пожалуйста разобраться с этим утверждением.

Критерий Эйлера: Пусть $p>2$. Число $a$ взаимно-простое с $p$, является квадратичным вычетом по модулю $p$ тогда и только тогда, когда $a^{\frac{p-1}{2}}\equiv 1 \pmod p$

Необходимость: Пусть $a$ - квадратичный вычет, тогда существует $x$, которое взаимно с $p$ и $x^2\equiv a \pmod p$. Возводя обе части сравнения в степень $\frac{p-1}{2}$ мы получаем, что $x^{p-1}\equiv a^{\frac{p-1}{2}} \pmod p$ но малой теореме Ферма $x^{p-1}\equiv 1 \pmod p$ и отсюда заключаем, что $a^{\frac{p-1}{2}}\equiv 1 \pmod p$.

А вот как быть с достаточностью? т.е. если $a^{\frac{p-1}{2}}\equiv 1 \pmod p$, то $a$ будет квадратичным вычетом?

-- 21.07.2014, 11:11 --

Там как-то пользуются теоремой Лагранжа. но я смысл что-то уловить не могу

[Sonic86]

Ward в сообщении #889107 писал(а):

т.е. если $a^{\frac{p-1}{2}}\equiv 1 \pmod p$, то $a$ будет квадратичным вычетом?

Да.
Для доказательства можно воспользоваться цикличностью мультипликативной группы вычетов $\mathbb{Z}_p^{\times}$

[Ward]

Sonic86
А можно ли это доказать без цикличности. Мне интересно больше такое доказательство.

[Sonic86]

Ward в сообщении #889107 писал(а):

Там как-то пользуются теоремой Лагранжа. но я смысл что-то уловить не могу

Этой?:

Whitaker в сообщении #888498 писал(а):

Sonic86 писал(а):

А что за теорема Лагранжа?

Если у Вас есть сравнение $a_nx^n+\dots+a_1x+a_0\equiv 0\pmod p$, где $p$ - простое и $(a_n, p)=1$, то данное сравнение имеет не более $n$ решений.

Написал бы подробно как именно.
И вообще, какие факты доступны, какие - нет?

Рассматриваете уравнение $x^2\equiv 1\pmod p$?

-- Пн июл 21, 2014 07:23:37 --

Ward в сообщении #889121 писал(а):

А можно ли это доказать без цикличности. Мне интересно больше такое доказательство.

Эх, любят люди извращаться...

[Ward]

Да-да именно вот этой теоремой. Там говорят, что существует всего $\frac{p-1}{2}$ квадратичных вычетов по модулю $p$ и столько же квадратичных невычетов. Но я как-то не могу это понять.
Я был бы Вам крайне признателен если бы Вы мне это объяснили.

[bot]

Ward в сообщении #889124 писал(а):

Там говорят, что существует всего $\frac{p-1}{2}$ квадратичных вычетов

Правильно говорят - $\mathbb Z_p^*$ состоит из $p-1$ элементов: $\pm 1, \pm 2, \pm 3, \ldots \pm\frac{p-1}2$. Чтобы получить все квадратичные вычеты достаточно возвести в квадрат половину из них. Убедитесь, что все они будут разными.

[Sinoid]

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

Эх, любят люди извращаться...

До цикличности еще дорасти надо, я тоже цикличностью не знаю, а так, как просит ТС, читал.

[fractalon]

Доказать достаточность можно, пользуясь понятием первообразного корня. Первообразный корень $g$ по простому модулю $p$ - это такое g, что $\forall a \not\equiv 0 \pmod p \exists k: g^k \equiv a \pmod p$. Для простого модуля первообразный корень всегда существует.
В вышеизложенном предикате число $k$ называется индексом $a$ ($k=ind\ a$). Индекс - это что-то вроде логарифма по основанию первообразного корня (имеет те же свойства, что и логарифм, для умножения, деления, возведения в степень операнда). У каждого различного по модулю $p$ числа есть свой уникальный (по модулю $\varphi (p)=p-1$) индекс. При возведении числа в квадрат индекс, очевидно, увеличивается в два раза. Модуль $p-1$ чётный (при $p>2$), так что квадратичным вычетом число является тогда и только тогда, когда его индекс чётен.
Докажем теперь достаточность от противного. Пусть $a^{\frac{p-1}{2}} \equiv 1 \pmod p$ и $a$ - квадратичный невычет. В этом случае индекс $a$ нечётен. Но по свойству индекса (аналогичному свойству логарифма) из $a^{\frac{p-1}{2}} \equiv 1 \pmod p$ следует, что $\frac{p-1}{2} {ind\ a} \equiv 0 \pmod {p-1}$ (помним, что $ind\ 1 = 0$, как и у логарифма). При нечётном $ind\ a$ очевидно, что равенство неверно. Мы пришли к противоречию.

[bot]

Это конечно замечательно, но всё просто напросто вытекает из сравнения (для краткости $p'=\frac{p-1}{2}$)

$$\left(a^{p'}-1\right)\left(a^{p'}+1\right)\equiv 0 \pmod{p}$$

Все квадратичные вычеты, как Вы показали, удовлетворяют сравнению $\left(a^{p'}-1\right)\equiv 0 \pmod{p}$ и их столько, какова степень. Оставшиеся (а остались невычеты) удовлетворяют $\left(a^{p'}+1\right)\equiv 0 \pmod{p}$.

[Sonic86]

(Оффтоп)

fractalon в сообщении #889379 писал(а):

Первообразный корень $g$ по простому модулю $p$ - это такое g, что $\forall a \not\equiv 0 \pmod p \exists k: g^k \equiv a \pmod p$. Для простого модуля первообразный корень всегда существует.

Угу. Проще говоря

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

цикличностью мультипликативной группы вычетов $\mathbb{Z}_p^{\times}$

Однако

Ward в сообщении #889121 писал(а):

А можно ли это доказать без цикличности. Мне интересно больше такое доказательство.