Нахождение НОК с помощью разложения чисел на простые множители

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

Вычисление наименьшего общего кратного (НОК) через НОД(наименьший общий делитель)

Один из способов нахождения наименьшего общего кратного основан на связи между НОК и НОД. Существующая связь между НОК и НОД позволяет вычислять наименьшее общее кратное двух целых положительных чисел через известный наибольший общий делитель. Соответствующая формула имеет вид НОК(a, b)=a·b:НОД(a, b). Рассмотрим примеры нахождения НОК по приведенной формуле.

Пример.

Найдите наименьшее общее кратное двух чисел 126 и 70.

Решение.

В этом примере a=126, b=70. Воспользуемся связью НОК с НОД, выражающуюся формулой НОК(a, b)=a·b:НОД(a, b). То есть, сначала нам предстоит найти наибольший общий делитель чисел 70 и 126, после чего мы сможем вычислить НОК этих чисел по записанной формуле.

Найдем НОД(126, 70), используя алгоритм Евклида: 126=70·1+56, 70=56·1+14, 56=14·4, следовательно, НОД(126, 70)=14.

Теперь находим требуемое наименьшее общее кратное: НОК(126, 70)=126·70:НОД(126, 70)=126·70:14=630.

Ответ:

НОК(126, 70)=630.

Пример.

Чему равно НОК(68, 34)?

Решение.

Так как 68 делится нацело на 34, то НОД(68, 34)=34. Теперь вычисляем наименьшее общее кратное: НОК(68, 34)=68·34:НОД(68, 34)=68·34:34=68.

Ответ:

НОК(68, 34)=68.

Заметим, что предыдущий пример подходит под следующее правило нахождения НОК для целых положительные чисел a и b: если число a делится на b, то наименьшее общее кратное этих чисел равно a.

Нахождение НОК с помощью разложения чисел на простые множители

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

Озвученное правило нахождения НОК следует из равенства НОК(a, b)=a·b:НОД(a, b). Действительно, произведение чисел a и b равно произведению всех множителей, участвующих в разложениях чисел a и b. В свою очередь НОД(a, b) равен произведению всех простых множителей, одновременно присутствующих в разложениях чисел a и b (о чем написано в разделе нахождение НОД с помощью разложения чисел на простые множители).

Приведем пример. Пусть мы знаем, что 75=3·5·5 и 210=2·3·5·7. Составим произведение из всех множителей данных разложений: 2·3·3·5·5·5·7. Теперь из этого произведения исключим все множители, присутствующие и в разложении числа 75 и в разложении числа 210 (такими множителями являются 3 и 5), тогда произведение примет вид 2·3·5·5·7. Значение этого произведения равно наименьшему общему кратному чисел 75 и 210, то есть, НОК(75, 210)= 2·3·5·5·7=1 050.

Пример.

Разложив числа 441 и 700 на простые множители, найдите наименьшее общее кратное этих чисел.

Решение.

Разложим числа 441 и 700 на простые множители:

Получаем 441=3·3·7·7 и 700=2·2·5·5·7.

Теперь составим произведение из всех множителей, участвующих в разложениях данных чисел: 2·2·3·3·5·5·7·7·7. Исключим из этого произведения все множители, одновременно присутствующие в обоих разложениях (такой множитель только один – это число 7): 2·2·3·3·5·5·7·7. Таким образом, НОК(441, 700)=2·2·3·3·5·5·7·7=44 100.

Ответ:

НОК(441, 700)= 44 100.

Правило нахождения НОК с использованием разложения чисел на простые множители можно сформулировать немного иначе. Если ко множителям из разложения числа a добавить недостающие множители из разложения числа b, то значение полученного произведения будет равно наименьшему общему кратному чисел a и b.

Для примера возьмем все те же числа 75 и 210, их разложения на простые множители таковы: 75=3·5·5 и 210=2·3·5·7. Ко множителям 3, 5 и 5 из разложения числа 75 добавляем недостающие множители 2 и 7 из разложения числа 210, получаем произведение 2·3·5·5·7, значение которого равно НОК(75, 210).

Пример.

Найдите наименьшее общее кратное чисел 84 и 648.

Решение.

Получаем сначала разложения чисел 84 и 648 на простые множители. Они имеют вид 84=2·2·3·7 и 648=2·2·2·3·3·3·3. К множителям 2, 2, 3 и 7 из разложения числа 84 добавляем недостающие множители 2, 3, 3 и 3 из разложения числа 648, получаем произведение 2·2·2·3·3·3·3·7, которое равно 4 536. Таким образом, искомое наименьшее общее кратное чисел 84 и 648 равно 4 536.

Ответ:

НОК(84, 648)=4 536.