Составители:
Рубрика:
12
1.10. Показатели чисел по модулю и примитивные корни
Пусть (a, m) = 1. Рассмотрим бесконечную последовательность сте-
пеней числа a: a
0
= 1, a
1
, a
2
, a
3
, … В соответствии с теоремой Эйлера
существует целое положительное число s, такое, что
a
s
≡ 1 mod m. (1)
В самой теореме s = ϕ (m). Могут существовать и другие целые
положительные числа s, удовлетворяющие этому сравнению. Наимень-
шее из них обозначается e и называется показателем числа a по моду-
лю m. Иногда e называют порядком числа a по модулю m.
Набор степеней числа a вида: a
0
, a
1
, a
2
, a
3
, …, a
e–1
попарно не срав-
нимы между собой по модулю m. Докажем это. Пусть, например, при
некоторых n
1
и n
2
выполняется сравнение
a
n
1
≡ a
n
2
mod m,
где для определенности n
1
< n
2
< e. Умножим обе части сравнения на
a
e–n
2
, тогда получим: a
(e+n
1
–n
2
)
≡ 1 mod m. Но поскольку n
1
<n
2
, то в левой
части сравнения степень числа a меньше e, что противоречит тому, что
e – наименьшее число, удовлетворяющее сравнению ( 1 ).
Если найдется некоторое k, такое, что
a
k
≡ 1 mod m,
то e является делителем k. Очевидно, что всегда e является делите-
лем ϕ (m).
Пример. Возьмем m = 45, a = 2, (45, 2) = 1. Функция Эйлера ϕ (45) =
24. Следовательно, 2
24
≡ 1 mod 45. Число 24 представляется в канони-
ческой форме в виде: 24 = 2
3
3, т. е. имеет 8 разных делителей: 1, 2, 3, 4,
6, 8, 12, 24. Проверка показывает, что наименьшее число e = 12, так как
2
12
≡ 1 mod 45.
Если показатель e числа a по модулю m равен ϕ (m), то a называют
примитивным элементом по модулю m.
Пример. По каким модулям число a = 2 является примитивным
элементом ?
m = 3, 5, 7, 9, 11, 15, 17, 19.
1.11. Конечные поля (поля Галуа)
В пособии [3] приведены определения математических моделей с
одним классом объектов: групп, колец и полей. Не надеясь на то, что
студенты хорошо знакомы с этими определениями, повторим их.
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
