Лема Гаусса

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

Твердження

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

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

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

Доведення

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

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

xj\not \equiv xk{\pmod {p}}

і

xj\not \equiv -xk{\pmod {p}}

.

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

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

Див. також