Лемма Гаусса о квадратичных вычетах: различия между версиями
Перейти к навигации
Перейти к поиску
[непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
м оформление |
→Доказательство: оформление |
||
Строка 7: | Строка 7: | ||
== Доказательство == |
== Доказательство == |
||
Заметим что <math>a*2a*3a*....*\frac{p-1}{2}*a\equiv\left ( \frac{p-1}{2} \right )!*a^{p-1 |
Заметим что <math>a*2a*3a*....*\frac{p-1}{2}*a\equiv\left ( \frac{p-1}{2} \right )!*a^{\frac{p-1}{2}}\pmod{p}</math>. Заменим числа <math>k*a</math> большие чем <math>\frac{p}{2}</math> по модулю <math>p </math> на <math>(-1)*(p-k*a)</math>. Тогда слева вынесем <math>(-1)^v</math> и получим произведение некоторых <math> \frac{p-1}{2}</math> чисел по модулю <math>p</math> которые различны по модулю <math>p</math>(<math>(m\pm n)*a\not\equiv0\pmod{p}</math>) и дают остаток меньше <math>\frac{p}{2}</math>, значит это произведение сравнимо с <math>\left ( \frac{p-1}{2} \right )!</math>. Тогда мы можем сократить наше сравнение на <math>\left ( \frac{p-1}{2} \right )! </math> и получим что <math>(-1)^v \equiv a^{p-1/2}\pmod{p}</math>.По [[Критерий Эйлера|критерию Эйлера]] <math>a^{\frac{p-1}{2}}\equiv\left ( \frac{a}{p}\right)\pmod{p}</math>.<ref>{{Книга|автор=Дэвенпорт Г.|заглавие=Высшая арифметика. Введение в теорию чисел|ссылка=http://padabum.com/x.php?id=29017|ответственный=|издание=|место=|издательство=|год=|страницы=|страниц=|isbn=539701298X|isbn2=9785397012980}}</ref> |
||
== См. также == |
== См. также == |
Версия от 20:42, 8 ноября 2018
Лемма Гаусса позволяет определять является ли число квадратичным вычетом по модулю простого числа.
Формулировка
Возьмем простое и натуральное такое что . Посмотрим на остатки чисел по модулю . Пусть среди них остатков больших чем , тогда .
Доказательство
Заметим что . Заменим числа большие чем по модулю на . Тогда слева вынесем и получим произведение некоторых чисел по модулю которые различны по модулю () и дают остаток меньше , значит это произведение сравнимо с . Тогда мы можем сократить наше сравнение на и получим что .По критерию Эйлера .[1]
См. также
Литература
- ↑ Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — ISBN 539701298X. — ISBN 9785397012980.