Наименьшее общее кратное нескольких чисел

§ 101. Что такое наименьшее общее кратное. Наименьшим общим кратным нескольких данных чисел называется самое меньшее число, которое делится на каждое из этих чисел.

Так, для трех чисел: 6, 15 и 20 наименьшее общее кратное есть 60, так как никакое число меньше 60 не делится на 6, на 15 и на 20, а 60 делится на эти числа.

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

§ 102. Способ первый: посредством разложения на простые множители. Пусть требуется найти наименьшее общее кратное чисел: 100, 40 и 35. Для этого разложим каждое из этих чисел на простые множители:

100 = 2 · 2 · 5 · 5; 40 = 2 · 2 · 2 · 5; 35 = 5 · 7.

Чтобы какое-нибудь число делилось на 100, на 40 и на 35, необходимо и достаточно, чтобы в него входили все простые множители этих делителей. Выпишем все множители числа 100 и добавим к ним те множители числа 40, которых недостает в разложении 100. Тогда получим произведение 2 · 2 · 5 · 5 · 2, которое делится и на 100 и на 40. Добавим теперь к этому произведению те множители числа 35, которых в произведении недостает. Тогда получим произведение:

2 · 2 · 5 · 5 · 2 · 7 = 1400,

делящееся и на 100, и на 40, и на 35. Это и есть наименьшее общее кратное этих чисел, потому что, выключив из него хотя бы один сомножитель, мы получим число, которое не разделится на какое-нибудь из данных чисел.

Обратим внимание на то, что в рассмотренном примере мы, добавляя к простым множителям числа 100 недостающие в нем множители числа 40, добавили множитель 2. Хотя 2 в разложении числа 100 и имеется, но этот множитель там встречается всего 2 раза, а в разложения числа 10 мы видим сто 3 раза; поэтому мы и должны были считать его «недостающим» в разложении числа 100.

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

Пользуясь введенным в § 92 обозначением степени, мы можем разложение данных в пашем примере чисел записать так:

100 = 22 · 52;      40 = 23 · 5;      35 = 5 · 7.

Очевидно, что наименьшее общее кратное данных чисел должно содержать множители 2, 5 в 7; при этом множитель 2 должен входить в третьей степени, так как при меньшем показателе полученное число не могло бы делиться на 40; множитель 5 должен входить во второй степени, так как иначе полученное число не разделилось бы на 100; наконец, множитель 7 достаточно взять в первой степени. Таким образом, искомое наименьшее общее кратное есть

23 · 52 · 7 = 1400.

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

§ 103. Некоторые особые случаи. Рассмотрим два случая, в которых наименьшее общее кратное может быть найдено весьма просто.

Случай первый, когда никакая пара данных чисел не имеет общих множителей. Пусть, например, даны три числа: 20, 49, 33, из которых, как видно из разложений:

20 = 2 · 2 · 5, 49 = 7 · 7, 33 = 3 · 11,

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

2 · 2 · 5 · 7 · 7 · 3 · 11 = 20 · 49 · 33 = 32 340.

Так, в частности, надо поступать, когда отыскивается наименьшее общее кратное различных между собой простых чисел; например, наименьшее общее кратное чисел 3, 7 и 11 равно 3 · 7 · 11 = 231.

Случай второй, когда большее из данных чисел, делится на все остальные. Тогда наибольшее число и есть наименьшее общее кратное. Пусть, например, даны четыре числа: 5, 12, 15 и 60, из которых большее 60 делится на 5, на 12 и 15; так как оно при этом, конечно, делится и само на себя, то оно и есть наименьшее общее кратное.

§ 104. Способ второй: посредством нахождения наибольшего общего делителя.

Пусть требуется найти наименьшее общее кратное чисел 336 и 1260. Разлагая эти числа на простые множители, мы находим 336 = 24 · 3 · 7 и 1260 = 22 · 32 · 5 · 7. Произведение данных чисел равно

336 · 1260 = (24 · 3 · 7) · (22 · 32 · 5 · 7).      (1)

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

Таким образом, в наибольший общий делитель войдет 22, а в наименьшее общее кратное 24; в наибольший общий делитель войдет 3, а в наименьшее общее кратное 32; множитель 5, входящий в разложение только одного из двух данных чисел, войдет в их наименьшее общее кратное, а в наибольший общий делитель не войдет: наконец, множитель 7, который в каждое из данных чисел входит с показателем 1, войдет с этим показателем и в наибольший общий делитель, и в наименьшее общее кратное.

Таким образом, наибольший общий делитель данных чисел есть 22 · 3 · 7 = 84, а наименьшее общее кратное их 24 · 32 · 5 · 7 = 5070. Мы видим, что все множители данных чисел, стоящие в правой части равенства (1), распределились: часть из них вошла в наибольший общий делитель, а остальные вошли в наименьшее общее кратное. Поэтому произведение данных чисел 336 · 1260 равно произведению их наибольшего общего делителя 84 на их наименьшее общее кратное 5040. Отсюда получим:

Правило. Наименьшее общее кратное двух чисел равно произведению этих чисел, делимому на их наибольший общий делитель.

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

§ 105. Случай трех или более чисел. Пусть требуется найти наименьшее общее кратное трех чисел: 336, 1260 и 350. Находим сначала наименьшее общее кратное чисел 336 и 1260; оно равно 5040, как мы видели в § 104. Теперь находим наименьшее общее кратное числа 5040 и третьего данного числа 350. Наибольший общий делитель этих чисел легко найти (например, способом последовательного деления); он равен 70. Значит, наименьшее общее кратное чисел 5040 и 350 равно по правилу § 104:

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

Подобным же образом можно находить и наименьшее общее кратное четырех, пяти и более чисел.

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