сравнение (6) имеет единственное решение для х. В этом случае каждое число является А:-степенным вычетом и однозначно представимо в виде к-й степени. Другими словами, если к взаимно просто с р - 1, то числа

l 2 з(p-i)

сравнимы с числами 1, 2, 1, взятыми в каком-то другом

порядке. Например, если р = 19 и А; = 5, числа 1, 2, ..., 18 сравнимы по mod 19 с 1, 13, 15, 17, 9, 5, И, 12, 16, 3, 7, 8, 14, 10, 2, 4, 6, 18.

Совершенно другая ситуация возникает, если к и р-1 имеют обгций множитель. Рассмотрим сначала один частный случай, скажем, р = 19 и А: = 3. Сравнение (7) в этом случае имеет вид

3 = а (mod 18). Это сравнение, очевидно, неразрешимо, если а не делится на 3. Если а делится на 3, скажем а = ЗР последнее сравнение принимает вид = Р (mod 6). Это дает одно значение для по модулю 6, но три значения по модулю 18 (число 18 служит модулем, по которому определяется (), именно: Р Р + Р +12, если Р - одно из решений. Таким образом, если а делится на 3, то число а сравнимо с тремя различными кубами. Взяв таблицу индексов по модулю 19, мы увидим, что числа, индексы которых делятся на 3, равны 1, 7, 8, И, 12, 18. Если а - одно из этих чисел, то сравнение х = а (mod р) имеет точно три решения. Эти числа являются кубическими вычетами по mod 19, а оставшиеся 12 чисел - кубическими невычетами.

Обш;ий случай исследуется аналогично. Пусть К - наибольший обш;ий делитель к и р-1. Сравнение (7) неразрешимо относительно если а не делится на так как к и модуль делятся на К. С другой стороны, если а делится на сравнение (7) разрешимо относительно и имеет ровно К решений. Таким образом, к-степенными вычетами по mod р являются как раз те числа, индексы которых делятся на К, наибольший общий делитель к и р - 1. Если а есть А:-степенной вычет, сравнение (6) имеет ровно К решений.

Число А:-степенных вычетов равно так как индексами могут быть числа 1, 2, 1ив точности часть этих

чисел делится на К.

Простейшим является случай к = 2;в этом случае мы имеем дело с квадратичными вычетами и невычетами. Если предположить, что р > 2, то р - 1 четно и наибольший обш;ий делитель 2 и р - 1 равен 2. В этом случае заключение таково: квадратичные вычеты суть числа с четными индексами, а квадратичные невычеты - числа с нечетными индексами. Число тех и других одинаково и равно (р - 1). Если а - какой-нибудь квадратичный вычет, наша теория устанавливает, что сравнение х = = а (mod р) имеет точно два решения. Ясно, что если х = Xi - одно из решений, то х = -Xi - другое решение.

Если р = 19, то числа 1, 4, 5, 6, 7, 9, И, 16, 17 являются квадратичными вычетами, а числа 2, 3, 8, 10, 12, 13, 14, 15, 18 - квадратичными невычетами.

3. Квадратичные вычеты. В оставшейся части этой главы мы ограничимся теорией квадратичных вычетов и невычетов, которая может быть развита сугцественно дальше, чем об-ш;ая теория А:-степенных вычетов. Будем далее предполагать, что р - простое число, не равное 2.

Как мы уже видели, половина из чисел 1, 2, 1 -

квадратичные вычеты, другая половина - квадратичные невычеты. Квадратичные вычеты сравнимы с числами 1, 2, ..., ((р- 1)), ибо оставшиеся числа от (р + 1) до р - 1 после возведения в квадрат дают тот же результат:

{р - х) = х (mod р).

Квадратичные вычеты и невычеты обладают простым мультипликативным свойством. Произведение двух вычетов или двух невычетов является вычетом, а произведение вычета и невычета является невычетом. Это сразу следует из того, что вычеты имеют четные индексы, а невычеты - нечетные индексы: сумма двух четных или двух нечетных индексов четна, сумма же четного и нечетного индекса нечетна. Таким образом, например, в таблице квадратичных вычетов и невычетов для простого числа 19 в конце п. 2 произведение любых двух чисел, взятых из одной строки, сравнимо с некоторым числом из первой строки, а произведение двух чисел, взятых из разных строк, сравнимо с числом из второй строки.

Несомненно, что именно это мультипликативное свойство и навело Лежандра на мысль ввести символ квадратичного характера числа а по простому модулю р. Символ Лежандра определяется так:

а\ Г 1, если а - квадратичный вычет по mod р, pJ \ -сли а - квадратичный невычет по mod р.

Иногда мы будем использовать также обозначение {а\р). Другая форма этого определения такова: {а\р) = (-1)*, где а равно индексу а. Отмеченное выше мультипликативное свойство принимает вид

Любое число а (не сравнимое с 0) удовлетворяет сравнению Ферма а~ = 1 (modp). Так как р-1 - четно, это сравнение раскладывается на множители; полагая р - 1 = 2Р, можно сказать, что для каждого числа а либо = 1 (modp), либо

= -1 (modp). Эйлер, вероятно, первым заметил, что эти две возможности имеют место в зависимости от того, является а квадратичным вычетом или а есть квадратичный невычет. В нашем рассмотрении это доказывается тотчас же. Если а есть индекс а, то = q (mod р). Если а четно, то аР кратно р - 1 и д = 1 (mod р). Если а нечетно, то аР = (р - 1)а не кратно р - 1 и д* не сравнимо с 1, а следовательно, сравнимо с -1. Этот факт носит название критерия Эйлера для квадратичного характера а, В терминах символа Лежандра он принимает вид

-] =а (modp), (8)

гдеР=(р-1).

Критерий Эйлера сам по себе не приносит большой пользы при исследовании свойств квадратичных вычетов и невычетов, но из него тотчас же вытекает правило вычисления квадратичного характера от -1. Величина (-1) будет равна 1 или -1 в зависимости от того, четно Р или нет, т. е. в зависимости от того, имеет р вид 4А: + 1 или ik + 3. Отсюда следует, что -1 есть квадратичный вычет для простых вида 4А: + 1 квадратичный невычет для простых вида 4А: + 3. Это означает, что