Лема Гаусса

Лема Гаусса — результат у теорії чисел, який визначає, чи є деяке число квадратним лишком іншого числа. Умови леми важко перевірити на практиці, тож її значення для обчислень є невеликим, проте вона має значний теоретичний інтерес.

Твердження

Нехай маємо деяке просте число p і натуральне x, що не ділиться на p.Позначимо ${\displaystyle m={\frac {p-1}{2}}}$ Тоді

${\displaystyle \left({\frac {x}{p}}\right)=(-1)^{n}}$

де ${\displaystyle \left({\frac {x}{p}}\right)}$ — символ Лежандра, а n — число пар (j, u) таких, що ${\displaystyle 1\leq j\leq m}$ і ${\displaystyle 1\leq u\leq m}$ і виконується ${\displaystyle \ xj\equiv -u{\pmod {p}}}$

Доведення

Для кожного ${\displaystyle 1\leq j\leq m}$ існує єдине ${\displaystyle 1\leq u_{j}\leq m}$, таке, що виконується ${\displaystyle xj\equiv e_{j}u_{j}{\pmod {p}},}$ де ${\displaystyle e_{j}=1.}$ Тоді ${\displaystyle e_{1}e_{2}...e_{m}=(-1)^{n}}$.

Якщо j і k є двома різними числами від 1 до m тоді ${\displaystyle j\not \equiv k{\pmod {p}}}$ і ${\displaystyle j\not \equiv -k{\pmod {p}}}$. Як наслідок враховуючи, що p не ділить x маємо:

${\displaystyle xj\not \equiv xk{\pmod {p}}}$ і ${\displaystyle xj\not \equiv -xk{\pmod {p}}}$.

Тобто різним значенням ${\displaystyle 1\leq j\leq m}$ відповідають різні значення ${\displaystyle 1\leq u_{j}\leq m}$. Але тоді ${\displaystyle u_{1},u_{2},\ldots ,u_{m}=m!}$ Перемножуючи дві сторони рівностей ${\displaystyle xj\equiv e_{j}u_{j}{\pmod {p}},}$ для ${\displaystyle j=1,2,\ldots ,m}$ одержимо ${\displaystyle x^{m}m!\equiv (-1)^{n}m!{\pmod {p}},}$ і, враховуючи взаємну простоту p і m!, як наслідок ${\displaystyle x^{m}\equiv (-1)^{n}{\pmod {p}}}$.

Згідно з властивостями символу Лежандра ${\displaystyle x^{m}\equiv \left({\frac {x}{p}}\right){\pmod {p}}.}$ Звідси одержуємо ${\displaystyle \left({\frac {x}{p}}\right)\equiv (-1)^{n}{\pmod {p}}}$ і нарешті ${\displaystyle \left({\frac {x}{p}}\right)=(-1)^{n}}$.

Див. також

• Символ Лежандра
• Квадратичний закон взаємності