2А: + 1 = -2к (mod р). Подставляя эти значения, мы получаем

(Ь2.3-...-2А:)2 = -1 (modp),

так как число введенных отрицательных знаков равно 2к и является четным. Поэтому решениями сравнения х = -1 (mod р) являются числа х = ±(2А:)!, где р = ik + 1. Например, если р = = 13, так что А: = 3, то решениями служат х = ±6! = ±720 = = ±5 (mod 13). Эта конструкция, конечно, бесполезна для вычислений, но всегда интересно в дополнение к доказательству суш;ествования иметь и точную конструкцию.

4. Лемма Гаусса. Более глубокие свойства квадратичных вычетов и невычетов, в особенности свойства, связанные с законом взаимности (п. 5), были открыты эмпирически и впервые доказывались непрямыми и запутанными методами. Не ранее 1808 года (через семь лет после опубликования своих «Исследований») Гаусс открыл одну простую лемму, даюш;ую ключ к ясному и элементарному доказательству закона взаимности.

для простых вида 4А: + 1 ряды квадратичных вычетов и невычетов симметричны, так как значения характера от р - а и от а одинаковы. Действительно, р - а = -а и {-а\р) = {-1\р){а\р) = = {а\р). С другой стороны, если р имеет вид Ак + 3, характер р - а противоположен по знаку характеру а, что можно было заметить в случае р = 19 (в конце п. 2).

Тот факт, что сравнение х + 1 = О (mod р) разрешимо для простых вида 4А: + 1 и неразрешимо для простых вида 4А: + 3, был известен Ферма. После нескольких безуспешных попыток доказать этот факт Эйлер в 1749 году нашел доказательство; свой критерий он установил в 1755 году.

Лагранж в 1773 году заметил, что если рассматриваемое сравнение разрешимо, то суш;ествует очень простой способ точно указать его решения. При р = ik + l теорема Вильсона (П, 5) показывает, что 1-2-3-...-4А: = -1 (mod р).

4А: = - 1 (mod р), 4А: - 1 = -2 (mod р),

4] ЛЕММА ГАУССА 69

Лемма Гаусса дает правило для вычисления квадратичного характера числа а (не сравнимого с 0) по отногпению к простому р. Как всегда, мы предполагаем р > 2 и берем Р = (р - 1). Правило Гаусса предписывает образовать числа

а, 2а, За, ..., Ра (9)

и добиться, вычитая соответствующее кратное р, чтобы каждое из них лежало между - р и Пусть и - число отрицательных в образованном ряду чисел. Тогда {а\р) = (-1), т. е. а является квадратичным вычетом, если v четно, и квадратичным невычетом, если v нечетно. Доказательство этого факта совсем просто. Правило предписывает заменить каждое из чисел в ряду (9) сравнимым с ним числом из ряда ±1, ±2, ..., ±Р, что мы, очевидно, можем сделать. Если мы сделаем это, то ни одно число из ряда 1, 2, ..., Р не встретится более одного раза ни с плюсом, ни с минусом. Действительно, если бы какое-нибудь число встретилось дважды с одинаковым знаком, то в ряду (9) нашлись бы два числа, сравнимые друг с другом по mod р, чего нет; если же какое-нибудь число встретилось бы с противоположными знаками, то сумма двух чисел из ряда (9) была бы сравнима с нулем по mod р, чего также не может быть. Поэтому получающийся ряд состоит из чисел ±1, ±2, ..., ±Р, причем каждому приписан определенный знак. Перемножая два ряда, получаем

(а)(2а)(3а)... (Ра) = (±1)(±2)... (±Р) (mod р).

После сокращения на 2, 3, ..., Р отсюда следует, что

а(±1)(±1)...(±1) = (-1Г, где и - число знаков минус. В силу критерия Эйлера отсюда немедленно получается нужный результат. Чтобы проиллюстрировать лемму Гаусса численно, возьмем р = 19 и а = 5. Здесь Р = 9, и мы должны заменить числа 5, 10, 15, ..., 45 по mod 19 так, чтобы они лежали между -9 и 9 включительно. Получаются числа 5, -9, -4, 1, 6, -8, -3, 2, 7. Как и в общем случае, этими числами являются числа от 1 до 9, каждое со своим знаком. Число отрицательных знаков равно 4, и так как 4 четно, 5 является квадратичным вычетом по mod 19, или, символически: (519) = 1.

С помощью леммы Гаусса можно дать простое правило для нахождения квадратичного характера числа 2. Когда а = 2, ряд чисел в (9) таков: 2, 4, 6, ..2Р и 2Р = р - 1. Мы должны определить, сколько чисел в этом ряду после попадания в интервал между - р и р станут отрицательными. Так как рассматриваемые числа расположены между О и р, то отрицательными становятся числа, большие Поэтому мы должны найти, сколько чисел вида 2х удовлетворяет неравенству < 2х < р; другими словами, сколько найдется таких целых х, для которых р < 2х < \р. Положим р = 8А: + г, где г равно 1, 3, 5 или 7. В этих обозначениях наше условие имеет вид 2к+\г < х < 4А:+г; мы хотим узнать, четно или нет количество чисел х, удовлетворяющих этому условию. Четность количества этих чисел не нарушится, если вычесть из обеих частей неравенства четные числа 2к и Ак, Поэтому достаточно рассматривать неравенство

< X < \г. Это неравенство не имеет решения, если г равно 1; имеет одно решение при г, равном 3 или 5; и два решения, если г равно 7. Следовательно, 2 является квадратичным вычетом в первом и последнем случаях и невычетом в двух других случаях. Таким образом, имеет место следующее правило: 2 есть квадратичный вычет для простых вида Sk + l и квадратичный невычет для простых вида 8А:±3. Этот факт был известен Ферма, но доказали его впервые, причем очень сложным способом, Эйлер и Лагранж.

Поучительно получить с помощью леммы Гаусса еще одно правило такого же типа, ибо этот метод будет использован в следующем пункте для доказательства закона взаимности. Найдем, для каких простых 3 является вычетом и для каких - невычетом. Числа 3, 6, 9, ..., ЗР меньше р, следовательно, отрицательными после приведения к интервалу между -\р и \р будут только те из них, которые лежат между \р и р. Найдем число целых х, для которых \р <?>х < р или \р <х < \р. Положим р = 12А:+г, где г равно 1, 5, 7 или И (для простого, кроме случая, когда р равно 2 или 3, что исключается, имеются только эти возможности). Тогда неравенство принимает вид 2А:+ г < < < 4А: + г. Мы снова можем не обращать внимания на четные числа 2А: и 4А: и свести все к неравенству \г <х < г. Оно не имеет решения, если г равно 1; имеет одно решение, если г равно