2014 dxdy logo

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

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



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Критерий Эйлера
Сообщение21.07.2014, 09:32 


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

Критерий Эйлера: Пусть $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 10:20 


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

 Профиль  
                  
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 10:22 
Заслуженный участник


08/04/08
8331
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 


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

 Профиль  
                  
 
 Re: Критерий Эйлера
Сообщение21.07.2014, 12:27 
Заслуженный участник
Аватара пользователя


21/12/05
5475
Новосибирск
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 


03/06/12
1556
Sonic86 в сообщении #889122 писал(а):
Эх, любят люди извращаться...

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

 Профиль  
                  
 
 Re: Критерий Эйлера
Сообщение22.07.2014, 02:24 


08/09/13
165
Доказать достаточность можно, пользуясь понятием первообразного корня. Первообразный корень $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 
Заслуженный участник
Аватара пользователя


21/12/05
5475
Новосибирск
Это конечно замечательно, но всё просто напросто вытекает из сравнения (для краткости $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 
Заслуженный участник


08/04/08
8331

(Оффтоп)

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