Лема Гаусса

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

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

Твердження

[ред. | ред. код]

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

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

Доведення

[ред. | ред. код]

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

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

і .

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

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

Див. також

[ред. | ред. код]