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

Введем в рассмотрение символ Лежандра (читается: символ а по p; а называется числителем, p - знаменателем символа).

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

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

.

Доказательство: По теореме Ферма

a^p-1 ? 1(mod p), .

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

, (1)

. (2)

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

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

Пример 1: Имеем

5¹⁴ ? 1(mod 29).

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

Пример 2: Имеем

³¹⁴ ? -1(mod 29).

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

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

Если a ? a₁(mod p), то .

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

.

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

.

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

Так как - четное, если p вида 4m + 1, и нечетное, если p вида 4m + 3, то отсюда следует, что - 1 является квадратичным вычетом по модулю p, если p вида 4m + 1, и является квадратичным невычетом по модулю p, если p вида 4m + 3.

.

Доказательство: Имеем

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

,

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

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

a∙1 ? ε₁r₁(mod p),

a∙2 ? ε₂r₂(mod p),

..................... (3)

a∙p₁ ? ε_p1r_p1(mod p),

где ε_xr_x - абсолютно наименьший вычет ах, r_x - его модуль, так что ε_x = ±1.

Числа а∙1, -а∙1, а∙2, -а∙2, ... a∙p_l, -а∙р₁, образуют приведенную систему вычетов по модулю p (с, п.5, гл. III); их абсолютно наименьшие вычеты суть ε₁r₁ , -ε₁r₁ , ε₂r₂ , -ε₂r₂ ,…, ε_p1r_p1 , -ε_p1r_p1. Положительные из последних, т. е. r₁, r₂,…, r_p1 , должны совпадать с числами 1, 2, …, p₁ (b, п. 4, гл. III).

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

1 2 … p₁ = r₁ r₂… r_p1,

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

, (4)

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

,

что будет четным или нечетным, в зависимости от того, будет ли наименьший неотрицательный вычет числа ах меньше или больше , т. е. будет ли ε_x = 1 или ε_x = -1. Отсюда, очевидно,

,

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

.

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

,

откуда

(5)

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

.

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

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

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

.

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

Если оба числа p и q вида 4m + 3, то

;

если же хоть одно из них вида 4m + 1, то

.

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

. (6)

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

x = 1, 2, ..., р₁, у = 1, 2, ..., q₁.

Никогда не может быть qx = py, потому что из этого равенства следовало бы, что py кратно q, что ввиду (p, q) = (y, q) = 1 (Так как 0 < у < q) невозможно. Поэтому мы можем положить p₁q₁ = S₁ + S₂, где S₁ - число пар с qx < py и S₂ - число пар с py < qx.

Очевидно, S₁ есть также число пар с (этому не противоречит неравенство x ≤ p₁, так как из следует ). Поэтому

.

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

.

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

,

поэтому

,

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