Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел

Лекция 47. Алгоритмы нахождения НОД и НОК

План:

1. Разложение составного числа на простые множители (основная теорема арифметики).

2. Алгоритмы нахождения наибольшего общего делителя и наименьшего общего кратного данных чисел с помощью канонического разложения и алгоритма Евклида.

Рассмотрим сначала cпособ, основанный на разложении данных чисел на простые множители.

Пусть даны два числа 3600 и 288. Представим их в канони­ческом виде: 3600 = 2⁴·3²·5²;

288 = 2⁵·3². Найдем наибольший общий делитель данных чисел. В его разложение должны вой­ти все общие простые множители, которые содержатся в раз­ложениях чисел 3600 и 288, причем каждый из них нужно взять с наименьшим показателем, с каким он входит в оба разложения. Следовательно, D(3600,288) = 2⁴·3² = 144.

Вообще чтобы найти наибольший общий делитель данных чисел:

1) представляют каждое данное число в каноническом виде;

2) образуют произведение общих для всех данных чисел простых множителей, каждый с наименьшим показателем, каким он входит во все разложения данных чисел;

3) находят значение этого произведения - оно и будет наи­большим общим делителем данных чисел. Найдем наименьшее общее кратное чисел 3600 и 288. В его разложение должны войти все простые множители, которые содержатся хотя бы в одном из разложений чисел 3600 и 288, причем каждый из них нужно взять с наибольшим показате­лем, с каким он входит в оба разложения.

Следовательно, К(3600, 288) = 2⁵·3²·5 = 7200.

Вообще, чтобы найти наименьшее общее кратное данных
чисел:

1) представляют каждое данное число в каноническом виде;

2) образуют произведение всех простых множителей, на­ходящихся в разложениях данных чисел, каждый с наиболь­шим показателем, с каким он входит во все разложения дан­ных чисел;

3) находят значения этого произведения, оно и будет наи­меньшим общим кратным данных чисел.

Задача 1. Найти наибольший общий делитель и наи­меньшее общее кратное чисел 60, 252 и 264.

Решение. Представим каждое число в каноническом виде: 60 = 2²·3·5,

252 = 2²·3²·7, 264 = 2³·3·11.

Чтобы найти наибольший общий делитель данных чисел, образуем произведение общих для всех данных разложений простых множителей, каждый с наименьшим показателем, с каким он входит во все решения данных чисел: D(60,252,264) = = 2²·3= 12.

Наименьшее общее кратное чисел можно найти, образовав произведение всех простых множителей, находящихся в данных разложениях, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел, т.е. К(60, 252, 264) = 2³·3²·5·7·11 = 27720.

Задача 2. Найти наибольший общий делитель и наи­меньшее общее кратное чисел 48 и 245.

Решение. Представим каждое число в каноническом ви­де: 48 = 2⁴·3, 245 = 5·7².

Так как разложения данных чисел не содержат общих про-
стых множителей, то D(48, 245) = 1, а K(48, 245) = 48·245 =
= 10760.

Отыскание наибольшего общего делителя двух натуральных чисел по их каноническому виду требует предварительного разложения чисел на простые множители. Это несложно сде­лать, если числа не велики, но для многозначных чисел найти их каноническое разложение бывает трудно. Существует способ отыскания наибольшего общего делителя, требующий лишь деления с остатком. Этот способ был предложен Евклидом, и его называют алгоритмом Евклида. Он основан на следующих трех утверждениях, доказательство которых мы опускаем:

1. Если а делится на b, то D (a, b) = b.

2. Если а = bq + r и r < b, то множество общих делителей чи­сел а и b совпадает с множеством общих делителей чисел b и г.

3. Если а = bq + r и r < Ь, то D(a, b) = D(b, r).
Сформулируем теперь алгоритм Евклида для нахождения наибольшего общего делителя натуральных чисел а и b.

Пусть а > b.

Если а делится на b, то D(a;b) - b.

Если при делении а на b, получается остаток r, то a = bq + r и D(а, b) = D(b,r) и задача свелась к отысканию наибольшего общего делителя чисел b и r.

Если b делится на r, то D(b, r) = r и тогда D(a, b) = r.

Если при делении b на r получается остаток r,, то b = rq, + r, и поэтому D(r,r,) = D(b,r) = D(a,b).

Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В конце концов получим остаток, на кото­рый будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим дели­телем чисел a и b.

Найдем при помощи алгоритма Евклида наибольший об­щий делитель чисел 2585 и 7975. Делим уголком. Получаем: 7975 = 2585 ∙ 3 + 220, 2585 = 220 ∙ 11 + 165, 220 = 165∙ 1 + 55, 165 = 55 ∙ 3 + 0. В последнем случае остаток равен нулю. Значит, D (7975, 2575) = 55.

Упражнения

1. Найдите наибольший общий делитель и наименьшее общее кратное данных чисел, представив их в каноническом виде:
а) 948 и 624; 6) 120, 540, 418.

2. Используя алгоритм Евклида, найдите наибольший об­щий делитель чисел.

а) 846 и 246; б) 585 и 1960; в) 15283 и 10013.

3. Верно ли, что: а) D(448,656) = 16; б) K(578, 8670) = 8670?

4. Докажите, что числа 432 и 385 взаимно простые.

5. Найдите наибольший общий делитель всех пятизначных чисел, записанных при помощи цифр 1, 2, 3, 4, 5 (цифры в записи чисел не повторяются).

93. Основные выводы § 18

Изучая материал данного параграфа, мы определили сле­дующие понятия:

- делитель данного числа;

- простое число;

- составное число;

- общий делитель данных чисел;

-наибольший общий Делитель данных чисел;

- взаимно простые числа;

- общее краткое данных чисел;

-наименьшее общее кратное данных чисел.

Рассмотрены, а в ряде случаев и доказаны теоремы о свой­ствах делимости и признаках делимости на 2, 3, 4, 5,9. Кроме того, дан способ получения признаков делимости на те со­ставные числа, которые можно представить в виде произведе­ния взаимно простых чисел.

Любое составное число можно представить в виде произ-
ведения простых множителей или разложить на простые
множители.

Наибольший общий делитель двух чисел Можно находить двумя способами. Первый основан на разложении данных чисел на простые множители, а второй является алгоритмом Евклида.

Наименьшее общее кратное двух чисел можно находить, используя разложение данных чисел на простые множители, или, если известен наибольший общий делитель чисел а и b, то по формуле

a·b

K(a,b )= ־־־־־־־

D(a,b)