Лабораторная работа № 11 Первообразные корни и индексы.
Определение 1: Показателем (порядком) целого числа a по данному модулю m называется наименьшее целое положительное число, обозначаемое через 
, которое удовлетворяет следующему сравнению: 
.
Пример 1. Найти 
.
Составим последовательно сравнения вида 
. Наименьшее значение k, при котором получим b=1 и будет искомой характеристикой.
Следовательно, =5.
Теорема 1: Справедливы следующие утверждения:
1. Если 
.
2. Если 
3. 
Теорема 2: Сравнение 
имеет место тогда и только тогда, когда 
.
Определение 2: Класс вычетов 
называется первообразным корнем по модулю m, если показатель класса вычетов равен функции Эйлера, т.е. 
. Вместе с классом 
мы будем называть первообразными корнями и все числа этого класса.
Чтобы убедиться, что а, где (а,m)=1, - первообразный корень по модулю m, достаточно проверить, что 
, где к – собственные делители 
.
Пример 2. По модулю 54 класс 
- первообразный корень. Действительно, 
. Собственные делители равны k = {1, 2, 3, 6, 9}. Легко проверить, что 
при всех k.
Первообразные корни существуют не для всех модулей, а только для модулей вида 1,
, где p – нечетное простое число, 
.
Для нахождения первообразного корня по простому модулю m можно пользоваться следующим критерием:
Лемма: Пусть 
и 
- различные простые делители числа с. Для того чтобы число g, (g, m)=1 было первообразным корнем по модулю m, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений
.
Пример 3: Найти первообразный корень по модулю 41.
Решение: Имеем 
. Следовательно, для того чтобы число g было первообразным корнем по модулю 41, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений:
Испытывая числа 2,3,4,…, находим
Отсюда видим, что число 6 – первообразный корень, так как оно не удовлетворяет ни одному из сравнений (*).
Определение 3. Пусть 
. Число s называется индексом числа b по модулю m и основанию a, если имеет место сравнение: 
.
. Пример 4. Так как 
.
Ввиду практической пользы индексов для каждого простого модуля p (не слишком большого) составлены таблицы индексов (см. например в [1]). Это две таблицы: одна – для нахождения индекса по числу, другая – для нахождения числа по индексу.
Пример 5. Построить таблицы индексов для модуля p=41.
В примере 3 было показано, что первообразным корнем по модулю 41 является число. Его мы и примем за основание индексов. Находим сравнения (сравнения берутся по модулю 41):
| N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 26 | 15 | 12 | 22 | 1 | 39 | 38 | 30 | |
| 1 | 8 | 3 | 27 | 31 | 25 | 37 | 24 | 33 | 16 | 9 |
| 2 | 34 | 14 | 29 | 36 | 13 | 4 | 17 | 5 | 11 | 7 |
| 3 | 23 | 28 | 10 | 18 | 19 | 21 | 2 | 32 | 35 | 6 |
| 4 | 20 |
| I | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 1 | 6 | 36 | 11 | 25 | 27 | 39 | 29 | 10 | 19 |
| 1 | 32 | 28 | 4 | 24 | 21 | 3 | 18 | 26 | 33 | 34 |
| 2 | 40 | 35 | 5 | 30 | 16 | 14 | 2 | 12 | 31 | 22 |
| 3 | 9 | 13 | 37 | 17 | 20 | 38 | 23 | 15 | 8 | 7 |
Здесь, номер строки указывает число десятков, номер столбца – число единиц. Так, например, чтобы найти ind 25 воспользуемся таблицей слева.
Искомый индекс находится на пересечении 2 строки и 5 столбца и равен 4. Число, индекс которого равен 33 найдем из второй таблицы на пересечении 3 строки и 3 столбца. Это число 17.Теорема 3. Пусть 
- первообразный корень по модулю m, (b,m)=1. Тогда сравнение 
имеет место тогда и только тогда, когда 
.
Теорема 4. Пусть - первообразный корень по модулю m, 
. Тогда
1. 
2. 
.
Теорема 5. Пусть p – простое, нечетное, , m – одно из чисел 
, , (n,c)=d. Тогда сравнение 
разрешимо тогда и только тогда, когда ind a по основанию g кратен d и в этом случае оно имеет d решений.
Пример 5. Для сравнения 
имеем (8, 40)= 8, причем 
не делится на 8 и значит сравнение неразрешимо.
Пример 6. Для сравнения 
имеем (3,40)=1 и, следовательно, сравнение разрешимо. Из теоремы 4 следует, что выполняется
.
Пример 7. Решить сравнение: 
.
Имеем 
.
Задания для самостоятельной работы:
1. Составить таблицы индексов по модулю 7 и 11.
2. Решить сравнения, пользуясь таблицами индексов:
