2014 dxdy logo

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

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




 
 Критерий Эйлера
Сообщение21.07.2014, 09:32 
Всем привет!
Помогите пожалуйста разобраться с этим утверждением.

Критерий Эйлера: Пусть $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 --

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

 
 
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 10:17 
Ward в сообщении #889107 писал(а):
т.е. если $a^{\frac{p-1}{2}}\equiv 1 \pmod p$, то $a$ будет квадратичным вычетом?
Да.
Для доказательства можно воспользоваться цикличностью мультипликативной группы вычетов $\mathbb{Z}_p^{\times}$

 
 
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 10:20 
Sonic86
А можно ли это доказать без цикличности. Мне интересно больше такое доказательство.

 
 
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 10:22 
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 писал(а):
А можно ли это доказать без цикличности. Мне интересно больше такое доказательство.
Эх, любят люди извращаться...

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

 
 
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 12:27 
Аватара пользователя
Ward в сообщении #889124 писал(а):
Там говорят, что существует всего $\frac{p-1}{2}$ квадратичных вычетов

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

 
 
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 23:20 
Sonic86 в сообщении #889122 писал(а):
Эх, любят люди извращаться...

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

 
 
 
 Re: Критерий Эйлера
Сообщение22.07.2014, 02:24 
Доказать достаточность можно, пользуясь понятием первообразного корня. Первообразный корень $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$ очевидно, что равенство неверно. Мы пришли к противоречию.

 
 
 
 Re: Критерий Эйлера
Сообщение22.07.2014, 14:39 
Аватара пользователя
Это конечно замечательно, но всё просто напросто вытекает из сравнения (для краткости $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}$.

 
 
 
 Re: Критерий Эйлера
Сообщение22.07.2014, 19:19 

(Оффтоп)

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 писал(а):
А можно ли это доказать без цикличности. Мне интересно больше такое доказательство.

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


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