нение имеет не более d решений; мы должны доказать, что оно имеет точно d решений. Доказательство опирается на то, что полином - 1 делит полином х~ - 1. Если мы напишем у вместо х и положим р - 1 = dl, то получим

х- -l = y-l = {y- l){y- + y- + ... + у + i).

Так как у - 1 = х - 1, это дает тождество вида

где f{x) - некоторый полином от х степени р - 1 - d. Но сравнение х~ - 1 = 0 (mod р) имеет р-1 решений: оно удовлетворяется для всех X, не сравнимых с О (II, 3). Все р-1 решений должны удовлетворять одному из сравнений

х - 1 = О (mod р) или f{x) = 0 (mod р).

Последнее из них по теореме Лагранжа имеет не более р-1 - d решений, поэтому первое должно иметь не менее d решений, а значит, оно имеет ровно d решений. Взяв d равным или q~, получаем то, что нам осталось доказать.

Мы проиллюстрируем доказательство, взяв р = 19. Имеем р-1 = 2 • 3. Найдем прежде всего число Xi порядка 2, т. е. число X, для которого х = 1 и хф1. Очевидно, что Xi должно быть равно -1 или (что то же самое) 18. Найдем, далее, число Х2 порядка 9, т. е. число, удовлетворяюш;ее сравнениям х = 1 и хф1. Можно установить, что решениями х = 1 (mod 19) являются числа 1, 4, 5, 6, 7, 9, И, 16, 17. Из них числа 1, 7, И должны быть выкинуты, ибо для них будет выполняться сравнение х = 1. Остается шесть возможностей для Х2 это соответствует тому, что в обгцем случае имеется q - q~ выборов. Умножая эти оставшиеся числа на Xi, получаем первообразные корни -4, -5, -6, -9, -16, -17 или 2, 3, 10, 13, 14, 15. Чтобы установить, что 2 есть первообразный корень, найдем последовательные степени 2 по модулю 19, ими являются числа: 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1; впервые число 1 встречается на восемнадцатом месте. Вышеуказанный метод практически не очень удобен для нахождения первообразного корня: много прош;е испытывать числа 2, 3, ... подряд. Но это, конечно, не приводит к обгцему доказательству сугцествования первообразного корня.

Перемножив соответствуюш,ие количества для Xi, Х2, ..

легко заметить, что получается не более

№-1)(?2"-!)••• возможных значений для j;2, ... Найденные таким способом первообразные корни действительно различны, и так получаются все первообразные корни, но мы не будем останавливаться на доказательстве этих фактов. Число первообразных корней совпадает с указанным выше произведением, которое равно (f{p - 1) (в силу равенства (8) главы П). Например, когда р = = 19, имеется (f{18) = 6 первообразных корней.

2. Индексы. Суш;ествование первообразного корня имеет не только теоретический интерес, но и дает новое средство для вычислений по простому модулю р. Эти вычисления аналогичны вычислениям с помош;ью логарифмов в обычной арифметике.

Пусть д - первообразный корень по mod р. Тогда числа

д.д,..., д- 1) (5)

не сравнимы между собой, так как д~ - первая степень д., сравнимая с 1. Ни одно из этих чисел не сравнимо также с 0. Поэтому они должны быть сравнимы с числами 1, 2, ..., р - 1 в некотором порядке. Пример в предыдуш;ем пункте иллюстрирует этот факт: степени 2 от 2 до 2 (= 1) сравнимы с 1, 2, ..., 18 по модулю 19 (в другом порядке).

Любое число, не сравнимое с О по mod р, сравнимо поэтому с одним из чисел ряда (5). Если а = д (modp), мы говорим, что а есть индекс (относительно примитивного корня д). Если а дано, то среди чисел О, 1, ..., р - 1 единственным способом определяется а. Но брать а среди этих чисел необязательно. Если а есть какое-нибудь другое число, для которого а = д\ можем свести а к числу упомянутого ряда, прибавляя или вычитая подходягцее кратное р-1] это не изменит значения д , так как д = 1. Приведенное значение а должно быть равно а, поэтому а = а (mod р-1).

Если р = 19 и 5 = 2, то индексы чисел 1, ..., 18 таковы:

Число: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Индекс: 18 1 13 2 16 14 6 3 8 17 12 15 5 7 11 4 10 9

Чтобы составить такую таблицу, мы сопоставляем индекс 1 первообразному корню (здесь 2), индекс 2 его квадрату (здесь 4) и так далее, вычисляя степени первообразного корня по модулю р (здесь 19). Таблицу индексов для всех простых, меньших 1000, в 1839 году опубликовал Якоби (под названием Canon Arithmeticus).

С помош;ью индексов действие умножения по mod р можно свести к действию сложения так же, как, используя логарифмы, можно свести обычное умножение к сложению (если ограничиться умножением положительных чисел). Если а и b - данные числа, а и /3 - их индексы, то а = д*, b = , откуда аЬ = д~ (все сравнения берутся по модулю р). Следовательно, индекс произведения аЬ равен а + Р или отличается от него на кратное р-1. Таким образом, чтобы перемножить два числа, находят в таблице их индексы, складывают эти индексы, затем переносят результат в ряд О, 1, ..., р - 1, вычитая из него, если понадобится, кратное р - 1, и, наконец, находят в таблице число с вычисленным индексом. Например, чтобы найти значение 10-12 (mod 19), мы из написанной выше таблицы берем соот-ветствуюгцие индексы: 17 и 15; сумма этих индексов, равная 32, приводится к 14 после вычитания 18 = р - 1; число с индексом 14 равно 6 - это и есть ответ. Тем же способом можно выполнять и деление по (mod р); для этого надо заменить сложение индексов вычитанием.

Использование индексов дает возможность исследовать структуру А:-степенных вычетов и невычетов по mod р. Мы хотим выяснить, разрешимо сравнение

= а (mod р) (6)

или нет. Если индексом х служит то индекс х будет равен или отличается от к на кратное р-1. Поэтому записанное выше сравнение эквивалентно следуюш;ему:

к = а (modp- 1), (7)

где а - индекс а. Это - линейное сравнение от неизвестного по модулю р-1.

Если к взаимно просто с р - 1, ситуация не сложна: линейное сравнение (7) однозначно разрешимо относительно поэтому