Дискретная математика. Теория чисел. Ерош И.Л. - 9 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

9
Поскольку a ≥ b > r
2
> r
3
> … ≥ 0 , то алгоритм имеет конечное число
шагов. Согласно указанным свойствам (a, b) = (b, r
2
) = (r
2
, r
3
) = … = r
n.
Таким образом, наибольший общий делитель чисел a и b равен пос-
леднему ненулевому остатку в последовательности равенств, т. е. r
n
.
А наименьшее общее кратное a и b равно:
[a, b] = ab/(a, b).
Упражнения
Используя алгоритм Эвклида, найти НОК и НОД чисел:
а) 575 и 155;
б) 840 и 188650;
в) 4851 и 29106;
г) 975 и 616.
Если два числа N
1
и N
2
представлены в канонической форме соот-
ветственно
N
1
= p
1
n
1
p
2
n
2
… p
s
n
s
,
N
2
=
p
1
m
1
p
2
m
2
… p
s
m
s
,
то НОК ( N
1
, N
2
) = p
1
max(n
1
, m
1
)
p
2
max(n
2
, m
2
)
p
s
max(n
s
,
m
s
)
,
а НОД ( N
1
, N
2
) = p
1
min(n
1
, m
1
)
p
2
min(n
2
, m
2
)
p
s
min(n
s
, m
s
)
Если в каноническом представлении одного из чисел отсутствует
какой-либо простой сомножитель, его можно ввести в нулевой степени.
Например, для чисел 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.
Упражнения
Найти НОК и НОД для пар чисел:
а) N
1
= 440 , N
2
= 6050;
б) N
1
= 234 , N
2
= 4125;
в) N
1
= 66550 , N
2
= 40131;
г) N
1
=388 , N
2
= 1647.

Страницы