Лема Гаусса

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

Твердження

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

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

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

Доведення

Для кожного $1\le j\le m$ існує єдине $1\le u_j\le m$, таке, що виконується $xj\equiv e_j{u}_j(\mathrm{mod}p),$ де $e_j=1.$ Тоді $e_1{e}_2...e_m=(-1{)}^n$.

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

$xj\equiv ̸xk(\mathrm{mod}p)$ і $xj\equiv ̸-xk(\mathrm{mod}p)$.

Тобто різним значенням $1\le j\le m$ відповідають різні значення $1\le u_j\le m$. Але тоді $u_1,u_2,\dots ,u_m=m!$ Перемножуючи дві сторони рівностей $xj\equiv e_j{u}_j(\mathrm{mod}p),$ для $j=1,2,\dots ,m$ одержимо $x^{m}m!\equiv (-1{)}^{n}m!(\mathrm{mod}p),$ і, враховуючи взаємну простоту p і m!, як наслідок $x^m\equiv (-1{)}^n(\mathrm{mod}p)$.

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

Див. також

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