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

UptoLike

ВУЗ: 

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

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

Рубрика: 

118
Упражнения.
Используя алгоритм Евклида, найти НОК и НОД чисел:
a) 575 и 155;
b) 840 и 188650;
c) 4851 и 29106;
d) 975 и 616.
Если два числа N
1
и N
2
представлены в канонической форме соот
ветственно:
12
11
2
... ,
s
nn n
s
Npp p1
12
21
2
... ,
s
mm m
s
Npp p1
то
НОК
12
11 22
min( , ) min( , ) min( , )
12 1 2
,;
ss
nm nm nm
s
NN p p p3
НОД
12
11 22
min( , ) min( , ) min( , )
12 1 2
,.
ss
nm nm nm
s
NN p p p3
Если в каноническом представлении одного из чисел отсутствует
какойлибо простой сомножитель, его можно ввести в нулевой степе
ни. Например, для чисел N
1
= 2
3
5
2
7
1
и N
2
= 3
1
5
1
11
2
, прежде чем нахо
дить НОК и НОД, требуется их привести к одинаковой форме, т. е. сде
лать так, чтобы в каноническом представлении обоих чисел присут
ствовали бы одинаковые простые числа в соответствующих степенях,
а именно: N
1
= 2
3
3
0
5
2
7
1
11
0
; N
2
= 2
0
3
1
5
1
7
0
11
2
. Тогда НОК (N
1
, N
2
) =
= 2
3
3
1
5
2
7
1
11
2
= 508200, НОД (N
1
, N
2
) = 2
0
3
0
5
1
7
0
11
0
= 5.
Упражнения.
Найти НОК и НОД для пар чисел:
a) N
1
= 440; N
2
= 6050;
b) N
1
= 234; N
2
= 4125;
c) N
1
= 66550; N
2
= 40131;
d) N
1
= 388; N
2
= 1647.
Приведенный алгоритм легко обобщается на произвольное количе
ство чисел, для которых требуется определить НОК и НОД.
Упражнения.
Найти НОК и НОД для следующих наборов чисел:
a) N
1
= 60; N
2
= 350; N
3
= 495;
b) N
1
= 265; N
2
= 104; N
3
= 93;
c) N
1
= 2100; N
2
= 630; N
3
= 5880; N
4
= 9450;
d) N
1
= 700; N
2
= 495; N
3
= 104;
e) N
1
= 103; N
2
= 260; N
3
= 121.
6.1.7. Функция Эйлера для натурального числа j(m)
Функция Эйлера j(m) определяется для всех целых чисел m как ко
личество чисел ряда 1, 2, 3, …, m взаимно простых с m. Так, j(1) = 1
(по определению), j(2) = 1, j(3) = 2, j(4) = 2, j(5) = 4 и т. д. Легко по
казать, что для m = p (простых чисел) j(p) = p–1. Для m = p
n
функция

Страницы