§ 4. Индексы по модулям

Пусть — простое нечетное, — одно из чисел -первообразный корень по модулю .

b. Если у пробегает наименьшие неотрицательные вычеты по модулю с, то пробегает приведенную систему вычетов по модулю .

Действительно, пробегает с чисел, взаимно простых с , и ввиду b, § 1, не сравнимых по модулю .

c. Для чисел а, взаимно простых с , введем понятие об индексе, представляющее аналогию понятию о логарифме; при этом первообразный корень играет роль, аналогичную роли основания логарифмов.

Если

(считаем ), то называется индексом числа а по модулю при основании и обозначается символом (точнее, .

Ввиду b всякое а, взаимно простое с , имеет некоторый единственный индекс у среди чисел ряда

Зная у, мы можем указать и все индексы числа а; согласно с, § 1 это будут все неотрицательные числа класса

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

d. Имеем

и, в частности,

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

откуда, перемножая, находим

Следовательно, - один из индексов произведения

Ввиду практической пользы индексов для каждого простого модуля (разумеется, не слишком большого) составлены таблицы индексов. Это две таблицы; одна — для нахождения индекса по числу, другая — для нахождения числа по индексу.

Таблицы содержат наименьшие неотрицательные вычеты чисел (приведенная система) и их наименьших индексов (полная система) соответственно по модулям

Пр имер. Построим указанные таблицы для модуля Выше было показано (пример 1, § 3), что перво образным корнем по модулю 41 будет ; его мы примем за основание индексов. Находим (сравнения берутся по модулю 41):

поэтому указанные таблицы будут

Здесь номер строки указывает число десятков, номер столбца — число единиц числа (индекса). В графе, общей указанным строке и столбцу, помещается соответствующий индекс (число).

Например, найдем в графе первой таблицы, общей строке с номером 2 и столбцу с номером 5, т. е. Число, индекс которого 33, найдем в графе второй таблицы, общей строке с номером 3 и столбцу с номером 3, т. е.