Общие теоремы

Из сравнений степени n > 1 в дальнейшем будут рассматриваться лишь простейшие, а именно - двучленные сравнения:

хⁿ º a(mod m); (а, m)=1. (1)

Если сравнение (1) имеет решения, то а называется вычетом степени n по модулю m.

В этой главе мы подробно рассмотрим случай n = 2 и в первую очередь рассмотрим двучленные сравнения второй степени по простому нечетному модулю p:

x² º а(mod p); (a, p)=1. (2)

Если а - квадратичный вычет по модулю p, то сравнение (2) имеет два решения.

Доказательство: Если а - квадратичный вычет, то сравнение (2) имеет, по крайней мере, одно решение x º x₁(mod p). Но тогда, ввиду , то же сравнение имеет и второе решение x º - x₁(mod p). Это второе решение отлично от первого, так как из x₁ º - x₁(mod p) мы имели бы 2x₁ º 0(mod p), что невозможно, ввиду (2, p)=(x₁, p)=1.

Указанными двумя решениями и исчерпываются все решения сравнения (2), так как последнее, будучи сравнением второй степени, более двух решений иметь не может (с, п. 4, гл. IV).

Приведенная система вычетов по модулю p состоит из квадратичных вычетов, сравнимых с числами

, (3)

и квадратичных невычетов.

Доказательство: Среди вычетов приведенной системы по модулю p квадратичными вычетами являются те и только те, которые сравнимы с квадратами чисел (приведенная система вычетов)

, (4)

т. е. с числами (3). При этом числа (3) по модулю p не сравнимы, так как из k² º l²(mod p), , следовало бы, что сравнению x² º l²(mod p), вопреки с, среди чисел (4) удовлетворяют четыре: x = - l, - k, k, l. 2