Квадратичные вычеты

(a) Рассмотрим — вычет и соответствующее ему число Заметим, что если и только если

а больше если (переход так как у нас — целое)

тогда логично рассмотреть если оно четно, то иначе больше. Тогда

Заметим, что

Тогда в получившейся сумме все большие заменим на тогда суммирование пройдет по всем от до то есть

(b) Докажем сначала лемму.

Лемма. Пусть и  — различные простые нечетные числа. Рассмотрим прямоугольник на целочисленной решетке с вершинами в точках Посчитав точки внутри и на границе этого прямоугольника, докажите, что

Доказательство. Рассмотрим прямоугольник как область:

Всего точек в

Прямая делит прямоугольник Количество точек под этой прямой для равно Сумма даёт общее количество точек под прямой

Аналогично, сумма соответствует точкам над прямой

Так как и — различные простые числа, они взаимно просты. Следовательно, прямая не проходит через целые точки внутри Таким образом количество точек в равно:

______________________________________________________________________________________________________________________________________________________

Рассмотрим из предыдущего пункта, только добавим индекс снизу — рассматриваем по модулю тогда получим, что

По предыдущему пункту

а по лемме, это равно тогда и получаем необходимое: