Дискретная математика. Ерош И.Л - 120 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

120
2
11
º 1 mod 23. Полученное сравнение элементарно проверяется:
2048 º 1 mod 23.
Теорема Эйлера.
Если m >1 и (a, m) = 1, то a
j(m)
º 1 mod m. Эта теорема обобщает
теорему Ферма, так как при m = p, j(m = p) = p–1.
Пусть m = 18, a = 5. Очевидно, что (5, 18) = 1.
Функция Эйлера j(m = 18) = 6. Поэтому 5
6
º 1 mod 18. Это сравне
ние проверяется достаточно просто: 5
2
º 7 mod 18, следовательно,
((5
2
))
3
º 7
3
= 343 º 1 mod 18.
Упражнения.
На основании теорем Ферма и Эйлера доказать справедливость срав
нений:
a) 2
36
º 3
36
º … º 36
36
º 1 mod 37;
b) 2
100
º 3
100
º … º 100
100
º 1 mod 101;
c) 2
8
º 4
8
º 7
8
º 8
8
º 11
8
º 13
8
º 14
8
º 1 mod 15.
6.1.10. Показатели чисел по модулю и примитивные корни
Пусть (a, m) = 1. Рассмотрим бесконечную последовательность сте
пеней числа a: a
0
= 1, a
1
, a
2
, a
3
, … В соответствии с теоремой Эйлера
существует целое положительное число s, такое, что
a
s
º 1 mod m. (6.1)
В самой теореме s = j(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
выполняется сравнение
12
mod ,
nn
aa m1 где для оп
ределенности n
1
< n
2
< e. Умножим обе части сравнения на
2
,
en
a
тог
да получим
1
2
12
1mod .
en n
am3
Но поскольку n
1
<n
2
, то в левой части
сравнения степень числа a меньше e, что противоречит тому, что e –
наименьшее число, удовлетворяющее сравнению (6.1). Если найдется
некоторое k, такое, что a
k
º 1 mod m, то e является делителем k. Оче
видно, что всегда e является делителем j(m).
Пример.
Возьмем m = 45, a = 2, (45, 2) = 1. Функция Эйлера j(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.

Страницы