Лема Гауса

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Твердження[ред.ред. код]

Нехай маємо деяке просте число 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_ju_j \pmod{p}, де e_j=1. Тоді e_1e_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_ju_j \pmod{p}, для j=1,2,\ldots,m одержимо x^mm! \equiv (-1)^nm! \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

Див. також[ред.ред. код]