Перейти к содержанию

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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

Возьмем простое [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]

Примечания

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