Лема Гауса

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

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

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

Нехай маємо деяке просте число p і натуральне x, що не ділиться на p.Позначимо Тоді

де символ Лежандра, а n— число пар (j,u) таких, що і і виконується

Доведення[ред.ред. код]

Для кожного існує єдине таке що виконується де Тоді

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

і

Тобто різним значенням відповідають різні значення . Але тоді Перемножуючи дві сторони рівностей для одержимо і, враховуючи взаємну простоту p і m!, як наслідок

Згідно з властивостями символу Лежандра Звідси одержуємо і нарешті

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