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

Для термина «Лемма Гаусса» см. также другие значения.

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

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

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