§ 4. Индексы по модулям
Пусть — простое нечетное, — одно из чисел -первообразный корень по модулю .
b. Если у пробегает наименьшие неотрицательные вычеты по модулю с, то пробегает приведенную систему вычетов по модулю .
Действительно, пробегает с чисел, взаимно простых с , и ввиду b, § 1, не сравнимых по модулю .
c. Для чисел а, взаимно простых с , введем понятие об индексе, представляющее аналогию понятию о логарифме; при этом первообразный корень играет роль, аналогичную роли основания логарифмов.
Если
(считаем ), то называется индексом числа а по модулю при основании и обозначается символом (точнее, .
Ввиду b всякое а, взаимно простое с , имеет некоторый единственный индекс у среди чисел ряда
Зная у, мы можем указать и все индексы числа а; согласно с, § 1 это будут все неотрицательные числа класса
Непосредственно из данного здесь определения индекса следует, что числа с данным индексом у образуют класс чисел по модулю .
d. Имеем
и, в частности,
Действительно,
откуда, перемножая, находим
Следовательно, - один из индексов произведения
Ввиду практической пользы индексов для каждого простого модуля (разумеется, не слишком большого) составлены таблицы индексов. Это две таблицы; одна — для нахождения индекса по числу, другая — для нахождения числа по индексу.
Таблицы содержат наименьшие неотрицательные вычеты чисел (приведенная система) и их наименьших индексов (полная система) соответственно по модулям
Пр имер. Построим указанные таблицы для модуля Выше было показано (пример 1, § 3), что перво образным корнем по модулю 41 будет ; его мы примем за основание индексов. Находим (сравнения берутся по модулю 41):
поэтому указанные таблицы будут
Здесь номер строки указывает число десятков, номер столбца — число единиц числа (индекса). В графе, общей указанным строке и столбцу, помещается соответствующий индекс (число).
Например, найдем в графе первой таблицы, общей строке с номером 2 и столбцу с номером 5, т. е. Число, индекс которого 33, найдем в графе второй таблицы, общей строке с номером 3 и столбцу с номером 3, т. е.