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

a. Пусть - каноническое разложение числа m. Пусть далее c и c₀ имеют значения, указанные в теореме 1, п.

b. Если

, , …, , (1)

то система γ, γ₀, γ₁, …, γ_k называется системой индексов числа а по модулю m.

Из такого определения следует, что γ, γ₀ – система индексов числа а по модулю 2^α, а γ₁, …, γ_k – индексы числа a по модулям . Поэтому (g, п. 6; с, п. 4) всякое a, взаимно простое с т (тем самым оно взаимно простое и со всеми , имеет единственную систему индексов γ', γ₀', γ₁', …, γ_k' среди cc₀c₁…c_k = φ(m) систем γ, γ₀, γ₁, …, γ_k, которые получим, заставляя γ, γ₀, γ₁, …, γ_k независимо друг от друга пробегать наименьшие неотрицательные вычеты по модулям c, c₀, c₁, …, c_k, а все системы индексов числа a суть все системы γ, γ₀, γ₁, …, γ_k, составленные из неотрицательных чисел классов

γ ? γ'(mod c), γ₀ ? γ₀'(mod c), γ₁? γ₁(mod c), …, γ_k ? γ_k'(mod c).

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

c. Так как индексы γ, γ₀, γ₁, …, γ_k числа a по модулю m являются индексами его соответственно по модулям , то верна теорема:

Теорема 3

Индексы произведения сравнимы по модулям c, c₀, c₁, …, c_k с суммами индексов сомножителей.

d. Пусть τ = φ(2^α) при α ≤ 2 и при α > 2 и пусть h - наименьшее общее кратное чисел τ, c₁, …, c_k. При всяком a, взаимно простом с m, сравнение a^h ? 1 верно по всем модулям , значит, это сравнение верно и по модулю m. Поэтому a не может быть первообразным корнем по модулю m в тех случаях, когда h < φ(m). Но последнее имеет место при α > 2, при k > 1, а также при α = 2, k = 1. Поэтому для m > 1 первообразные корни могут существовать лишь в случаях . Но как раз для этих случаев существование первообразных корней было доказано выше (п. 6, 2). Поэтому

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

.

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

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

(-1)⁰ = 1, (-1)¹ = 1,

5⁰ = 1, 5¹ = 5,

- 5⁰ ? 7(mod 8), - 5¹ ? 3(mod 8).

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

Пример: Построим таблицу индексов по модулю 40. Здесь имеем 40 = 8∙5, причем для каждого числа N приведенной системы вычетов по модулю 40 мы значения индексов γ и γ₀ найдем в таблице индексов по модулю 8 предыдущего примера, а значения индекса γ₁ найдем в таблице индексов по модулю 5, т. е. в таблице

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

Пример: Построим таблицу индексов по модулю 9 и таблицу индексов по модулю 18.

5⁰ ? 1, 5¹ ? 5, 5² ? 7, 5³ ? 8, 5⁴ ? 4, 5⁵ ? 2.

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

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

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

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

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

Глава 1