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

UptoLike

ВУЗ: 

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

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

Рубрика: 

119
Эйлера j(p
n
) = p
n–1
(p–1). Для произвольного числа m, представленно
го в канонической форме
12
1
2
... ,
s
nn n
s
mpp p1
функция Эйлера определя
ется следующим образом: j(m) = m(1–1/p
1
)(1–1/p
2
)…(1–1/p
s
).
Например: j(11) = 10; j(9) = 6; j(18) = 6.
Упражнения.
Вычислить функцию Эйлера j(m) для чисел m = 7, 12, 15, 17, 23,
24, 25, 28, 37, 54, 64.
6.1.8. Сравнимость чисел и классы вычетов
Выпишем все числа от 1 до 8 и вычеркнем все числа не взаимно про
стые с 8. Количество оставшихся чисел равно j(m = 8) = 4, а сами эти
числа (1, 3, 5, 7). Множество этих чисел обладает свойством замкнуто
сти относительно операции умножения по модулю m = 8. Действитель
но, перемножая любые пары чисел из множества (1, 3, 5, 7) и находя
наименьший положительный остаток по модулю m = 8, будем получать
всегда одно из этих же чисел. Каждое из этих чисел порождает беско
нечный счетный класс чисел: 1+8·t; 3+8·t; 5+8·t; 7+8·t, где t – любое
целое.
Более того, множество классов с порождающими элементами в виде
этих чисел обладает свойством замкнутости, а именно: при любых це
лых t произведение представителей классов (1+8·t; 3+8·t; 5+8·t; 7+8·t)
дает в результате представителя одного из этих же классов.
Можно показать, что классы вычетов, получаемые в соответствии с
функцией Эйлера, всегда образуют абелеву группу по умножению. А это,
в частности, означает, что для любого представителя из этих классов
можно найти обратный элемент из представителей этих же классов.
Упражнения.
Постройте абелевы группы классов, порождаемые числами 10, 12,
15, 18, 21, 24, 25, 27, 28.
6.1.9. Теоремы Ферма и Эйлера
Теорема Ферма.
Существует мнение, что Ферма не публиковал свои научные труды,
а формулировал свои знаменитые теоремы либо в письмах к знакомым ма
тематикам, либо на полях рукописей. Так, на полях одной из рукописей Фер
ма написал, что если p – простое число и (a, p) = 1, то a
p–1
º 1 mod p.
Пусть p = 23, a = 18. Очевидно, что (23, 18) = 1, следовательно,
18
22
º 1 mod 23. Проверить этот результат несложно. Для этого заме
тим, что 18 º –5 mod 23, поэтому можно написать эквивалентное срав
нение: (–5)
22
º 1 mod 23 или 5
22
º 1 mod 23. Последнее сравнение мож
но представить в виде (5
2
)
11
º 1 mod 23, и так как 25 º 2 mod 23, то

Страницы