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

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

ФормулировкаПравить

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

ДоказательствоПравить

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

ПримечанияПравить