ГЛАВА III

КВАДРАТИЧНЫЕ ВЫЧЕТЫ

1. Первообразные корни. В этой главе мы будем исследовать алгебраические сравнения по простому модулю, содержа-гцие только два члена, т. е. кроме константы один член. Такое двучленное сравнение можно записать в виде

ах = b (mod р)

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

х = аЬ (mod р).

Мы можем поэтому привести любое двучленное сравнение к простейшему виду:

х = с {modp). (1)

Число, для которого сравнение (1) разрешимо, называется к-степенным вычетом по модулю р; аналогично, если это сравнение неразрешимо, говорят, что с есть к-степенной невычет. (Удобно, однако, числа с, сравнимые с О (mod)), не относить к /с-степенным вычетам, хотя в этом случае сравнение и разрешимо.) Если к равно 2, мы получаем квадратичные вычеты и невычеты; так как в этом случае теория может быть развита дальше, чем в обгцем случае, то в настоягцей главе будет рассматриваться именно эта возможность.

Чтобы проиллюстрировать это определение, положим р равным 13, а /с равным 2 или 3. Значения х и х по модулю 13 таковы:

я;: 1 2 3 4 5 6 7 8 9 10 11 12 х. I А 9 3 12 10 10 12 3 9 4 1 я;: 1 8 1 12 8 8 5 5 1 12 5 12

Таким образом, по модулю 13 числа 1, 3, 4, 9, 10, 12 - квадратичные вычеты, а оставшиеся числа 2, 5, 6, 7, 8, И - квадратичные невычеты. Числа 1, 5, 8, 12 - кубические вычеты, а оставшиеся числа 2, 3, 4, 6, 7, 9, 10, И - кубические невычеты.

Теория /с-степенных вычетов и невычетов связана с понятием порядка числа по модулю р, который был определен в (II, 3). Порядок любого числа а (предполагается, что а не сравнимо с 0) - это наименьшее натуральное число, для которого = 1 (mod р). Мы доказали, что / является делителем - 1, а в примере с р = 11 нашли, что порядок 2 точно равен - 1. Эйлер первым сформулировал теорему о том, что для любого простого числа р найдется число, порядок которого равен р - 1, и назвал такое число первообразным корнем для простого р. Но его доказательство сугцествования первообразного корня было неудовлетворительным; первое удовлетворительное доказательство было дано Лежандром. К изложению этого доказательства мы теперь и приступаем.

Первый шаг доказательства состоит в установлении одного обгцего принципа, касаюгцегося порядка произведения двух чисел. Если число а имеет порядок /, а число b - порядок к, причем I и к взаимно просты, то произведение аЬ имеет порядок 1к. Конечно, число а6, возведенное в степень 1к, дает 1 (mod р), потому что

{аЪ) = {а){ЬУ = 1 (mod р)

(так как = 1 (mod р) и b = 1 (mod р)). Этот факт не зависит от взаимной простоты а и 6, но он показывает лишь, что порядок аЬ является делителем 1к. Может быть, этот порядок - собственный делитель 1к; мы должны доказать, что на самом деле это не так. Предположим, что порядок аЬ равен liki, где li - делитель /, а fci - делитель к. Тогда

Возведем обе части этого сравнения в степень I2, где /1/2 = I-Так как = 1, то мы получаем, что Ь = 1. Из этого следует, что Iki кратно порядку 6, который равен к.Ио I взаимно просто с к, значит ki кратно к; будучи также делителем к, ki должно быть равно к. Аналогично /1 = / и, таким образом, порядок аЬ в точности равен 1к.

1] ПЕРВООБРАЗНЫЕ КОРНИ 61

Этот принцип дает возможность строить первообразный корень шаг за шагом. Пусть р-1 разложено в произведение степеней простых, скажем

p-l = q,q,\.. (2)

Допустим, что мы нашли число Xi порядок которого равен q, число X2j порядок которого равен 2% и так далее. Тогда, применив несколько раз только что доказанный принцип, мы убедимся, что произведение найденных чисел имеет порядок р-1 и, значит, является первообразным корнем. Поэтому остается лишь доказать, что если q - одна из степеней простых, со-ставляютих р - 1, то сутествует число, порядок которого по mod р в точности равен q.

Число, порядок которого равен q, должно удовлетворять сравнению

х = 1 (mod р), (3)

Но число, удовлетворяюш;ее этому сравнению, не обязано иметь порядок q\ его порядок может быть любым делителем q, т. е. он может быть равен 1 или q, или q и так далее до q~. Но если порядок не равен q, то он является делителем q~и число х должно удовлетворять сравнению

х"" = 1 (modp). (4)

Следовательно, нам нужно найти число, удовлетворяюш;ее сравнению (3), но не удовлетворяюгцее сравнению (4).

Мы можем доказать сугцествование такого числа, подсчитав, сколько решений имеют эти сравнения. Конечно, по теореме Лагранжа сравнение (3) имеет не более q решений, а сравнение (4) имеет не более q~ решений. Само по себе это не помогло бы нам, но, к счастью, можно доказать, что эти сравнения имеют в точности q и q~ решений. Отсюда уже следует, что имеется qci qa-i чисел, удовлетворяюш;их (3) и не удовлетворяюш;их (4), а так как q > q~j то это дает нужный результат и заканчивает доказательство.

Мы рассмотрим более обш;ий случай, именно, рассмотрим сравнение

j; - 1 = О (mod р), где d - любой делитель р - 1. По теореме Лагранжа это срав-