Лемма Гаусса о квадратичных вычетах

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая Дзяніс Тутэйшы (обсуждение | вклад) в 15:43, 19 июля 2018 (оформление). Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску


Лемма Гаусса позволяет определять является ли число квадратичным вычетом по модулю простого числа.

Формулировка

Возьмем простое и натуральное такое что . Посмотрим на остатки чисел по модулю . Пусть среди них остатков больших чем , тогда .

Доказательство

Заметим что . Заменим числа большие чем по модулю на . Тогда слева вынесем и получим произведение некоторых чисел по модулю которые различны по модулю () и дают остаток меньше , значит это произведение сравнимо с . Тогда мы можем сократить наше сравнение на и получим что .По критерию Эйлера .[1]

См. также

Литература

  1. Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — ISBN 539701298X. — ISBN 9785397012980.