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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение. Представим каждое число в каноническом виде:        60 =  252 = , 264 = .

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

Наименьшее общее кратное чисел можно найти, образовав произведение всех простых множителей, находящихся в данных разложениях, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел, т. е. K(60;252;264)==27720.

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

Решение. Представим каждое число в каноническом виде         48 = , 245 = 5·.

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

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

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

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

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

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

Пусть a > b.

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

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

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

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

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

Задача 42. Найти при помощи алгоритма Евклида наибольший общий делитель чисел 2585 и 7975.

Решение. Процесс последовательного деления будем записывать так:

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

Задача 43. Мимо станции железной дороги проходят один за другим три поезда: в первом – 418 пассажиров, во втором – 494 и в третьем – 456. Сколько пассажирских вагонов в каждом поезде, если известно, что в каждом вагоне находится одинаковое количество пассажиров и их число наибольшее из всех возможных?

Решение. Чтобы ответить на вопрос задачи, надо узнать, сколько пассажиров в каждом вагоне. Из условия задачи известно, что в каждом вагоне находится одинаковое количество пассажиров и их число наибольшее из возможных. Поэтому это число является наибольшим общим делителем чисел 494, 418, 456. Представим каждое число в каноническом виде: 494 = 2·13·19, 418 = 2·11·19, 456 = ·3·19. Поэтому D(418, 494, 456) = 2·19 = 38. Значит, в каждом вагоне находится по
38 пассажиров. Тогда в первом поезде – 418 : 38 = 11 вагонов, во втором – 494 : 38 = 13 вагонов, в третьем  –  456: 38 = 12 вагонов.

Задача 44. Каждой наименьшей длины должны быть доски, чтобы их можно было разрезать поперек на куски длиной по 40 см, по 60 см, по 45 см, и чтобы при этом не получалось обрезков?

Решение. Длина каждой доски есть наименьшее общее кратное чисел 40, 60 и 45, так как она должна быть наименьшей и «делится без остатка» на куски длиной по 40 см, по 60 см, по 45 см. Представим каждое из чисел в каноническом виде: 40 = ·5, 60 = ·3·5, 45 = ·5. Поэтому K(40, 60, 45) = ··5 = 360. Значит, длина каждой доски должна быть 360 сантиметров.

Упражнения для самостоятельной работы

1. Найдите наибольший общий делитель и наименьшее общее кратное данных чисел, представив их в каноническом виде:

            а) 21120, 144, 1760; б) 1960, 588, 1430

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

а) 3825 и 43560;  б) 15283 и 10013;              в) 21120 и 30720.

3. Верно ли что:       

            а) D(448, 656) = 16;  б) K(578, 8670) = 8670?

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

5. Туристы прошли в первый день 36 километров, во второй – 32 километра и в третий – 24 километра, причем каждый день они были в пути целое число часов. Сколько часов они были в пути, если их скорость выражалась целым числом километров в час, была постоянной и наибольшей из возможных?

6. На столе лежат книги, не более 100. Определить их число, если известно, что их можно связывать в пачки по 3 книги, по 4 книги и даже по 5 книг.