§ 7. Индексы по любому составному модулю

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

b. Если

то система называется системой индексов числа а по модулю .

Из такого определения следует, что — система индексов числа а по модулю — индексы числа а по модулям . Поэтому (g, § 6; с, § 4) всякое а, взаимно простое с (тем самым оно взаимно простое и со всеми имеет единственную систему индексов среди ) систем которые получим, заставляя независимо друг от друга пробегать наименьшие неотрицательные вычеты по модулям , а все системы индексов числам суть все системы составленные из неотрицательных чисел классов

Числа а с данной системой индексов могут быть найдены путем решения системы (1), а следовательно ( § 3, гл. IV), образуют класс чисел по модулю .

c. Так как индексы числа а по модулю являются индексами его соответственно по модулям то верна теорема:

Индексы произведения сравнимы по модулям с суммами индексов сомножителей.

d. Пусть при при и пусть А — общее наименьшее кратное чисел При всяком а, взаимно простом с , сравнение верно по всем модулям значит, это сравнение верно и по модулю . Поэтому а не может быть первообразным корнем по модулю в тех случаях, когда . Но последнее имеет место при при , а также . Поэтому для первообразные корни могут существовать лишь в случаях . Но как раз для этих случаев существование первообразных корней было доказано выше (§§ 6, 2). Поэтому

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

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

Пример 1. Построим таблицу индексов по модулю 8. Здесь имеем и для каждого числа N приведенной системы вычетов по модулю 8 будем иметь , где равно одному из чисел 0, 1 (полная система вычетов по модулю с) и равно одному из чисел 0, 1 (полная система вычетов по модулю ). Находим

Поэтому таблица индексов по модулю 8 будет

Пример 2. Построим таблицу индексов по модулю 40. Здесь имеем причем для каждого числа N приведенной системы вычетов по модулю 40 мы значения индексов у и найдем в таблице индексов по модулю 8 примера 1, а значения индекса найдем в таблице индексов по модулю 5, т. е. в таблице

В результате получим следующую таблицу индексов по модулю 40:

Пример 3. Построим таблицу индексов по модулю 9 и таблицу индексов по модулю 18. Здесь имеем Число 5 будет первообразным корнем по модулю 9, так как оно не удовлетворяет ни одному из сравнений

При этом имеем (сравнения берутся по модулю 9):

Следовательно, таблица индексов по модулю 9 будет

А таблица индексов по модулю 18 будет

Пример 4. Построим таблицу индексов по модулю 21. Здесь имеем и для каждого числа N приведенной системы вычетов по модулю 21 мы значение индекса найдем в таблице индексов по модулю 3, т. е. в таблице

а значение индекса найдем в таблице индексов по модулю 7, т. е. в таблице

В результате получим следующую таблицу индексов по модулю 21: