Первообразные корни и индексы

Порядком числа а по модулю m называется наименьший натуральный показатель k такой, что a^k º 1(mod m). Порядок числа а по модулю m существует, если (a, m) = 1, и обозначается O (a mod m).

Теорема 8.1. Пусть O (a mod m) = d. Тогда

1. a^k º 1(mod m) Û k M d;

2. j(m) M d;

3. a^k º a^l (mod m) Û k º l (mod d);

4. Числа a, a ², …, a^d попарно несравнимы по модулю m.

Число а называется первообразным корнем по модулю m, если O (a mod m) = j(m). Первообразный корень существует не для всякого модуля. Для любого простого модуля первообразный корень существует.

Пусть а – первообразный корень по модулю m. Тогда (a, m) = 1 и числа a, a ², …, a^j(m) образуют приведенную систему вычетов по модулю m. Если (b, m) = 1, то индексом числа b по модулю m с основанием а называется показатель k такой, что a^k º b (mod m). Индекс обозначается ind_a b или ind b. Любые два индекса данного числа сравнимы по модулю j(m).

Пример 8.1. Найти первообразный корень по модулю 11 и построить таблицу индексов по этому модулю.

Решение. Имеем j(11) = 10. Значит, порядок любого числа по модулю 11 делит 10. Для числа 2 имеем 2² = 4 ≢ 1(mod 11); 2⁵ = 32 º -1 ≢ 1(mod 11); 2¹⁰ º 1(mod 11). Следовательно, O (2 mod 11) = 10 и 2 – первообразный корень по модулю 11. Если бы порядок числа 2 оказался меньше 10, то мы проверяли бы следующие числа.

Для построения таблицы индексов рассматриваем все степени числа 2 и определяем остаток от деления их на 10.

Отсюда получаем таблицу индексов. Для числа, расположенного во второй строке, индекс находится в первой строке того же столбца:

Теорема 8.2. Свойства индексов:

1. ind ab = ind a + ind b;

2. ind aⁿ = n ind a.

Свойства индексов позволяют решать двучленные сравнения с помощью таблицы индексов.

Пример 8.2. Решить сравнения: а) 7 х º 6 (mod 11); б) 5 х ⁸ º 3 (mod 11).

Решение.

а) 7 х º 6 (mod 11);

ind (7 х) º ind 6 (mod 10);

ind 7 + ind х º ind 6 (mod 10);

7 + ind х º 9 (mod 10);

ind х º 2 (mod 10);

х º 4 (mod 11).

б) 5 х ⁸ º 3 (mod 11);

ind 5 + 8 ind х º ind 3 (mod 10);

4 + 8 ind х º 8 (mod 10);

8 ind х º 4 (mod 10);

(8, 10) = 2, 4M2, следовательно, сравнение имеет два решения;

4 ind х º 2 (mod 5);

2 ind х º 1 (mod 5);

2 ind х º 6 (mod 5);

ind х º 3 (mod 5);

ind х º 3 (mod 10), ind х º 8 (mod 10);

х º 8 (mod 11), х º 3 (mod 11).

Упражнение 8.1. Решите сравнения с помощью таблицы индексов:

а) 5 х º 9 (mod 11);

б) 4 х º 7 (mod 11);

в) 6 х ⁶ º 5 (mod 11);

г) 6 х ⁶ º 7 (mod 11);

д) 3 х ⁷ º 8 (mod 11);

е) 8 х ⁸ º 7 (mod 11).

СИСТЕМАТИЧЕСКИЕ ДРОБИ

Любое рациональное число может быть записано в виде конечной или бесконечной периодической дроби в любой m -ичной позиционной системе счисления. В m -ичной записи числа

A = = ,

где 0 < A < 1, повторяющаяся последовательность цифр а ₁… а_k называется периодом, а расположенная перед ней после запятой последовательность b ₁… b_l – предпериодом. Длина периода и предпериода – это число цифр в них. Дробь называется чисто периодической, если предпериод в ней отсутствует.

Теорема 9.1. Если у рационального числа , записанного в виде несократимой дроби, знаменатель b взаимно прост с основанием системы m, то А записывается в виде чисто периодической m -ичной дроби, длина периода k которой есть порядок числа m по модулю b.

Если знаменатель дроби не взаимно прост с основанием системы m, то домножаем числитель на такую степень m, чтобы после сокращения со знаменателем в знаменателе осталось число, взаимно простое с m. Эта степень и есть длина предпериода. Если при этом в знаменателе останется 1, то m -ичная дробь будет конечной. Если знаменатель будет больше 1, то длина периода определяется с помощью теоремы 9.1. по получившейся дроби.

Пример 9.1. Найти длину предпериода и периода при разложении числа в 14-ричную дробь.

Решение. Имеем (36, 14) = 2 > 1. Поэтому производим преобразования:

.

Заключаем, что длина предпериода равна 2. Для нахождения длины периода вычисляем порядок O (14 mod 9). Имеем j(9) = 6, поэтому искомый порядок есть делитель числа 6. Проверяем последовательно эти делители:

14¹ º 5 (mod 9);

14² º 5² º 25 º -2(mod 9);

14³ = 14²×14 º (-2)×5 º -10 º -1(mod 9);

14⁶ º (-1)² º 1(mod 9).

Следовательно, длина периода равна 6.

Упражнение 9.1. Найдите длину предпериода и периода при разложении числа A в m -ичную дробь:

а) , m = 15; б) , m = 14; в) , m = 12.