Составители:
Рубрика:
10
Приведенный алгоритм легко обобщается на произвольное количе-
ство чисел, для которых требуется определить НОК и НОД.
Упражнения
Найти НОК и НОД для следующих наборов чисел:
а) N
1
= 60 , N
2
= 350 , N
3
= 495;
б) N
1
= 265 , N
2
= 104 , N
3
= 93;
в) N
1
= 2100 , N
2
= 630 , N
3
= 5880 , N
4
= 9450;
г) N
1
= 700 , N
2
= 495 , N
3
= 104;
д) N
1
= 103 , N
2
= 260 , N
3
= 121.
1.7. Функция Эйлера
ϕ ϕ
ϕ ϕ
ϕ (m)
Функция Эйлера ϕ(m) определяется для всех целых чисел m как ко-
личество чисел ряда 1, 2, 3, …, m взаимно простых с m. Так, ϕ(1) = 1 (по
определению), ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4 и т. д. Легко показать,
что для m = p – простых чисел ϕ(p) = p –1. Для m = p
n
функция Эйлера
ϕ(p
n
) = p
n–1
(p –1). Для произвольного числа m, представленного в кано-
нической форме, m = p
1
n
1
p
2
n
2
…p
s
n
s
функция Эйлера определяется следу-
ющим образом:
ϕ(m) = m(1–1/p
1
)(1–1/p
2
)…(1–1/p
s
).
Например, ϕ(11) = 10; ϕ(9) = 6; ϕ(18) = 6.
Упражнения
Вычислить функцию Эйлера ϕ(m) для чисел m = 7, 12, 15, 17, 23, 24,
25, 28, 37, 54, 64.
1.8. Сравнимость чисел и классы вычетов
Выпишем все числа от 1 до 8 и вычеркнем все числа не взаимно
простые с 8. Количество оставшихся чисел равно ϕ(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 – любое целое.
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
