WikiSort.ru - Не сортированное

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

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

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

См. также

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

Литература