Лемма Гаусса о квадратичных вычетах
Лемма Гаусса позволяет определять, является ли число квадратичным вычетом по модулю простого числа.
Формулировка
Возьмем простое [math]\displaystyle{ p }[/math] и натуральное [math]\displaystyle{ a }[/math] такое что [math]\displaystyle{ (a,p)=1 }[/math]. Посмотрим на остатки чисел [math]\displaystyle{ a,2\cdot a,3\cdot a,\dots\frac{p-1}{2}\cdot a }[/math] по модулю [math]\displaystyle{ p }[/math]. Пусть среди них [math]\displaystyle{ v }[/math] остатков больших чем [math]\displaystyle{ \frac{p}{2} }[/math], тогда [math]\displaystyle{ \left (\frac{a}{p} \right )=(-1)^v }[/math] (здесь использован символ Лежандра).
Доказательство
Рассмотрим произведение [math]\displaystyle{ a\cdot 2a\cdot 3a\cdots\frac{p-1}{2}\cdot a\equiv\left ( \frac{p-1}{2} \right )!\cdot a^{\frac{p-1}{2}}\pmod{p} }[/math]. Заменим числа [math]\displaystyle{ k\cdot a }[/math], большие чем [math]\displaystyle{ \frac{p}{2} }[/math] по модулю [math]\displaystyle{ p }[/math], на [math]\displaystyle{ (-1)\cdot (p-k\cdot a) }[/math]. Тогда слева вынесем [math]\displaystyle{ (-1)^v }[/math] и получим произведение некоторых [math]\displaystyle{ \frac{p-1}{2} }[/math] чисел по модулю [math]\displaystyle{ p }[/math], которые различны по модулю [math]\displaystyle{ p }[/math] ([math]\displaystyle{ (m\pm n)\cdot a\not\equiv0\pmod{p} }[/math]) и дают остаток меньше [math]\displaystyle{ \frac{p}{2} }[/math], значит это произведение сравнимо с [math]\displaystyle{ \left ( \frac{p-1}{2} \right )! }[/math]. Тогда мы можем сократить наше сравнение на [math]\displaystyle{ \left ( \frac{p-1}{2} \right )! }[/math] и получим что [math]\displaystyle{ (-1)^v \equiv a^{(p-1)/2}\pmod{p} }[/math]. По критерию Эйлера [math]\displaystyle{ a^{\frac{p-1}{2}}\equiv\left ( \frac{a}{p}\right)\pmod{p} }[/math].[1]
Примечания
- ↑ Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — ISBN 539701298X. — ISBN 9785397012980. Архивная копия от 30 сентября 2017 на Wayback Machine