Элементы теории чисел и криптозащита. Воронков Б.Н - 65 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

65
18. Функция Эйлера
18.1. Определение. Пусть n ≥ 1 и пусть
φ
(n) будет количеством це-
лых чисел х, удовлетворяющих неравенству 1 ≤ х ≤ n и (x, n) = 1. Функция
φ
называется функцией Эйлера, или функцией количества положительных
целых чисел, взаимно простых с n.
18.2. Примеры. Ясно, что
φ
(1) = 1,
φ
(2) = 1. Для некоторого n > 2 чис-
ла 1 и n – 1 будут взаимно простыми с n, так что
φ
(n) ≥ 2.
Если р – простое число, тогда все числа 1, 2, . . . , р – 1 будут взаимно
простыми с р и, следовательно,
φ
(р) = р – 1. Обратно, если n – составное
число и больше 1, тогда оно имеет некоторый делитель d, 1 < d < n, который
не будет взаимно простым с n. Следовательно,
φ
(n) < n – 1. Следовательно,
φ
(n) = n – 1, если и только если n будет простым числом.
Числа х, имеющие степени простого числа р
а
, для которых 1 ≤ х ≤ р
а
и
(х, р
а
) = 1, точно являются числами, которые не кратны р. Кратными р будут
р, 2р, 3р, . . . , р
а–1
р, количество которых равно
р
а–1
. Итак,
1
1
() 1
ааа а
ррр р
р
φ
−
⎛⎞
=− = −
⎜⎟
⎝⎠
.
Теперь попробуем найти общую формулу для нахождения
φ
(n). Сде-
лаем это на основе последнего примера п. 18.2 и следующего результата.
18.3. Теорема. Функция
φ
является мультипликативной, т. е., если
(m, n) = 1, тогда
φ
(mn) =
φ
(m)
φ
(n).
18.4. Следствие. Если
12
12
...
k
n
nn
k
npp p=
является разложением числа n
по степеням простых чисел (так что p
i
являются различными простыми чис-
лами и каждое n
i
> 1), тогда
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−=
kk
n
k
nn
ррр
n
р
р
р
р
р
pn
k
1
1...
1
1
1
1
1
1...
1
1
1
1)(
212
2
1
1
21
φ
.
18.5. Упражнения
1. Составьте таблицу значений функции Эйлера
φ
(р
а
) для малых про-
стых чисел р и целых чисел а ≥ 1 и, используя мультипликативное свойство,
найдите все значения n, для которых
φ
(n) = 6. (Более ценным упражнением
было бы найти все n для
φ
(n) = 48; оно имеет не менее 11 решений). Пока-
жите также, что не существует n, для которого
φ
(n) = 14. Полезным замеча-
нием будет то, что, если р – простое число и p | n, тогда (p – 1) |
φ
(n). Оно
управляет достаточно большим количеством простых делителей n. (Поэто-
му 14 не является значением
φ
(n), иногда оно называется неполным числом.

Страницы