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

Для начала скажем, что для простого числа не существует представления в виде . Это так из-за того что квадраты дают только остатки 0 и 1 по модулю 4, а значит может давать только остатки 0, 1 и 2.

Для начала докажем лемму Туэ.

Лемма Туэ. Пусть  — натуральное число, а  — целое. Тогда найдутся такие целые и , что , , и .

Доказательство. Рассмотрим такие пары (, ), что , (исключая (0, 0)). Вариантов для значения ровно (0, 1, ...., []) и вариантов для аналогично > , поэтому пар > или , но нам нужно выкинуть (0, 0), поэтому пар . Для каждой пары можно посчитать значение и либо у нас найдется такая пара, в которой делиться на , либо для всех пар значений не делится на . Тогда так как пар хотя бы , то найдутся 2 пары () и () такие, что для них и имеет одинаковый остаток по модулю . Тогда делиться на , и , то есть мы нашли подходящие и .

Возвращаемся к доказательству теоремы. Так как , то -1 — кв. вычет по модулю , поэтому существует такое , что . Найдем , по лемме Туэ для такого . Имеем , возведем данное сравнение в квадрат и получим , возьмем , получаем и , так как и , потому что простое и целое.
от 1 до и делится на , поэтому .