Индексы по простому модулю.

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

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

Если то k называется индексом числа а по модулю при основании g и обозначается символом а или . Если k — другое число, для которого , то и, согласно предложению Таким образом, множество индексов данного числа а образуют класс вычетов по модулю Из определения индекса вытекает, что из следует

Пример. Пусть Число 2 есть первообразный корень по модулю 13. Индексы чисел при основании таковы:

С помощью этой таблицы по данному числу а находится его индекс по модулю 13. Следующая таблица позволяет по данному индексу находить соответствующее число:

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

ТЕОРЕМА 5.12. Если числа а, b взаимно простые с — любое натуральное число, то

Доказательство. По определению индексов чисел а и b имеем:

отсюда находим произведение

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

Из сравнения следует, что

поэтому есть один из индексов степени , т. е.

Примеры. 1. Пусть тогда

2. Решить сравнение

Данное сравнение равносильно такому:

Отсюда следует, что

ТЕОРЕМА 5.12. Пусть — мультипликативная группа классов вычетов, взаимно простых с и С есть аддитивная группа классов вычетов по модулю Отображение , ставящее в соответствие каждому элементу а группы элемент а группы С, есть изоформизм группы на группу С.

Доказательство. Согласно определению индекса, соответствие является биективным. Кроме того, сохраняется операция умножения в группе так как из сравнения

следует, что

Следовательно, есть изоморфизм группы на группу С.

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