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

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

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

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