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

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

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

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

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

Заметим что $a*2a*3a*....*{\frac {p-1}{2}}*a\equiv \left({\frac {p-1}{2}}\right)!*a^{p-1/2}{\pmod {p}}$. Заменим числа $k*a$ большие чем ${\frac {p}{2}}$ по модулю $p$ на $(-1)*(p-k*a)$. Тогда слева вынесем $(-1)^{v}$ и получим произведение некоторых ${\frac {p-1}{2}}$ чисел по модулю $p$ которые различны по модулю $p$($(m\pm n)*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^{p-1/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}$.

См. также

• Критерий Эйлера
• Квадратичный вычет
• Символ Лежандра