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

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

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

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

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

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

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

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

K(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.

Наименьшее общее кратное чисел можно найти, образовав произве­дение всех простых множителей, находящихся в данных разложениях, каждый с наибольшим показателем, с каким он входит во все разложе­ния данных чисел, т.е. K(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 (а, b) = b.

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

3. Если а=bq+r и r<b, то D(а, b) = D(b, r).

Сформулируем теперь алгоритм Евклида для нахождения наиболь­шего общего делителя натуральных чисел а и b.

Пусть а>b.

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

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

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

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

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

Найдем при помощи алгоритма Евклида наибольший общий дели­тель чисел 2585 и 7975. Процесс последовательного деления будем записывать так:

 

_ 7975 2585

7755 3 975 = 2585 3 + 220.

_ 2585 220

220 11 2585 = 220 × 11 + 165

_ 385

220

_220 165

165 1 220 = 165 × 1 + 55

_ 165 55

165 3 165 = 55 × 3 + 0

В последнем случае остаток равен нулю. Значит, D (7975, 2585) = 55.