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

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

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

Возьмем простое $p$ и натуральное $a$ такое что $(a,p)=1$. Посмотрим на остатки чисел $a,2\cdot a,3\cdot a,\dots \frac{p-1}{2}\cdot a$ по модулю $p$. Пусть среди них $v$ остатков больших чем $\frac{p}{2}$, тогда $\left(\frac{a}{p}\right)=(-1{)}^v$ (здесь использован символ Лежандра).

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

Рассмотрим произведение $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}}(\mathrm{mod}p)$. Заменим числа $k\cdot a$, большие чем $\frac{p}{2}$ по модулю $p$, на $(-1)\cdot (p-k\cdot a)$. Тогда слева вынесем $(-1{)}^v$ и получим произведение некоторых $\frac{p-1}{2}$ чисел по модулю $p$, которые различны по модулю $p$ ($(m\pm n)\cdot a\equiv ̸0(\mathrm{mod}p)$) и дают остаток меньше $\frac{p}{2}$, значит это произведение сравнимо с $\left(\frac{p-1}{2}\right)!$. Тогда мы можем сократить наше сравнение на $\left(\frac{p-1}{2}\right)!$ и получим что $(-1{)}^v\equiv a^{(p-1)/2}(\mathrm{mod}p)$. По критерию Эйлера $a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p)$.