Показатели и первообразные корни

Пусть тогда делит Поскольку — простое, задача сводится к рассмотрению случаев.

Если то что невозможно.

Если то то есть но противоречие.

Если то откуда или но противоречие.

Случаи и влекут за собой сравнение Но То есть двойка — квадратичный вычет по модулю Заметим, что при нечётном простое число имеет вид (при число составное). Однако двойка не может быть квадратичным вычетом по простому модулю вида противоречие. Следовательно, что и требовалось.

Теперь докажем, что двойка не может быть квадратичным вычетом по простому модулю вида Остатки при делении на будем называть положительными, а остальные — отрицательными. Умножим все положительные остатки на Пусть среди полученных чисел есть отрицательных остатков. Тогда с одной стороны произведение этих остатков сравнимо с по модулю с другой стороны оно сравнимо с по модулю Отсюда получаем, что

Осталось заметить, что отрицательными будут лишь те, которые лежат между и (границы включены). Количество таких чисел равно верхней целой части от При оно нечётно, то есть Следовательно, двойка — квадратичный невычет, доказано.