§ 2. Символ Лежандра

a. Введем в рассмотрение символ Лежандра (читается: символ а. по ; а называется числителем, — знаменателем символа). Этот символ определяется для всех а, не делящихся на . Он задается равенством если а — квадратичный вычет по модулю , и равенством если а — квадратичный невычет по модулю .

b. Вычислить символ (и таким путем определить, является а квадратичным вычетом или же квадратичным невычетом по модулю ) позволяет следующая теорема (критерий Эйлера).

При а, не делящемся на , имеем

Действительно, по теореме Ферма

Один только один из сомножителей левой части последнего сравнения делится на (оба сомножителя не могут одновременно делиться на , в противном случае их разность 2 должна была бы делиться на ). Поэтому имеет место одно и только одно из сравнений

Но всякий квадратичный вычет а удовлетворяет при некотором сравнению и, следовательно, также получаемому из него почленным возведением в степеньсравнению (1). При этом квадратичными вычетами и исчерпываются все решения сравнения (1), так как, будучи сравнением степени оно не может иметь более чем решений.

Поэтому квадратичные невычеты удовлетворяют сравнению (2).

Пример 1. Имеем

Поэтому - квадратичный вычет по модулю 29 (сравнение имеет два решения). Пример 2. Имеем

Поэтому и - квадратичный невычет по модулю 29 (сравнение не имеет решений).

Далее мы выведем важнейшие свойства символа

c. Если , то

Это свойство следует из того, что числа одного и того же класса будут одновременно квадратичными вычетами или невычетами.

Действительно, и, следовательно, - квадратичный вычет.

Это свойство следует из b при .

Так как - четное, если вида и нечетное, если вида то отсюда следует, что —1 является квадратичным вычетом по модулю , если вида и является квадратичным невычетом по модулю , если вида

Действительно, имеем

откуда и вытекает наше утверждение. Отсюда следствие:

т. е. в числителе символа можно отбросить любой квадратичный множитель.

g. Чтобы вывести дальнейшие свойства символа Лежандра, мы сначала докажем некоторую вспомогательную формулу. Полагая рассмотрим сравнения

где — абсолютно наименьший вычет — его модуль, так что

Числа образуют приведенную систему вычетов по модулю (с, § 5, гл. III); их абсолютно наименьшие вычеты суть Положительные из последних, т. е. должны совпадать с числами (b, § 4, гл. III).

Перемножая теперь сравнения (3) и сокращая на

получим , откуда имеем

Далее находим

что будет четным или нечетным, в зависимости от того, будет ли наименьший неотрицательный вычет числа меньше или больше , т. е. будет ли или

Отсюда, очевидно,

и потому из (4) находим

Предполагая а нечетным, преобразуем последнее равенство. Имеем ( — четное)

откуда

Формула (5) и есть та, которую мы имели в виду доказать. Она позволит нам вывести еще два важнейших свойства символа Лежандра.

Следует из формулы (5) при

Но можно представить в виде где - одно из чисел 1, 3, 5, 7. При этом что будет четным при и будет нечетным при . Поэтому 2 будет квадратичным вычетом по модулю , если вида или вида и будет квадратичным невычетом по модулю , если вида или вида

I. Если - простые нечетные, то (закон взаимности квадратичных вычетов)

Так как будет нечетным лишь в случае, когда оба числа рад будут вида и четным, если хоть одно из этих чисел будет вида то указанное свойство можно формулировать так:

Если оба числа вида , то

Для доказательства заметим, что ввиду h формула (5) принимает вид

Полагая теперь рассмотрим пар чисел, получаемых, когда в выражениях числа х и у независимо друг от друга пробегают системы значений

Никогда не может быть потому что из этого равенства следовало бы, что кратно q, что ввиду (так как ) невозможно. Поэтому мы можем положить где - число пар с и - число пар с

Очевидно, есть также число пар с (этому не противоречит неравенство так как из следует Поэтому

Аналогичным путем убедимся, что

Но тогда равенство (6) дает нам

поэтому

откуда и следует отмеченное свойство.