Индексы по модулям рα в 2рα

a. Пусть p - простое нечетное, α ≥ 1; m - одно из чисел р^α и 2р^α; c = φ(m), g - первообразный корень по модулю m.

b.

Теорема 1

Если γ пробегает наименьшие неотрицательные вычеты γ = 0, 1, ..., с - 1 по модулю c, то g^γ пробегает приведенную систему вычетов по модулю m.

Доказательство: g^γ пробегает c чисел, взаимно простых с m, и ввиду Теоремы 1, п. 1, не сравнимых по модулю m.

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

Если

a = g^γ(mod m)

(считаем γ ≥ 0), то γ называется индексом числа a по модулю m при основании g и обозначается символом γ = ind a (точнее, γ = ind_g a).

Ввиду Теоремы 1 всякое a, взаимно простое с m, имеет некоторый единственный индекс γ' среди чисел ряда

γ = 0, 1, …, c - 1.

Зная γ', мы можем указать и все индексы числа a; согласно Теоремы 2, п. 1 это будут все неотрицательные числа класса

γ ? γ'(mod c).

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

d.

Теорема 2

Имеем

ind ab...l ? ind a + ind b+ ... + ind l(mod c)

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

ind aⁿ ? nind a(mod c).

Доказательство:

a ? g^{ind a}(mod m), b ? g^{ind b}(mod m), …, l ? g^{ind l}(mod m),

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

ab…l ? g^{ind a + ind b+ … + ind l}(mod m).

Следовательно, ind a + ind b+ … + ind l - один из индексов произведения ab...l.

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

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

6⁰ ? 1 6⁸ ? 10 6¹⁶ ? 18 6²⁴ ? 16 6³² ? 37

6¹ ? 6 6⁹ ? 19 6¹⁷ ? 26 6²⁵ ? 14 6³³ ? 17

6² ? 36 6¹⁰ ? 32 6¹⁸ ? 33 6²⁶ ? 2 6³⁴ ? 20

6³ ? 11 6¹¹ ? 28 6¹⁹ ? 34 6²⁷ ? 12 6³⁵ ? 38

6⁴ ? 25 6¹² ? 4 6²⁰ ? 40 6²⁸ ? 31 6³⁶ ? 23

6⁵ ? 27 6¹³ ? 24 6²¹ ? 35 6²⁹ ? 22 6³⁷ ? 15

6⁶ ? 39 6¹⁴ ? 21 6²² ? 5 6³⁰ ? 9 6³⁸ ? 8

6⁷ ? 29 6¹⁵ ? 3 6²³ ? 30 6³¹ ? 13 6³⁹ ? 7

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

p = 41, p - 1=2³∙5, g = 6

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

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