Делимость, признаки делимости

Нахождение наименьшего общего кратного, способы, примеры нахождения НОК.


Представленный ниже материал является логическим продолжением теории из статьи под заголовком НОК - наименьшее общее кратное, определение, примеры, связь между НОК и НОД. Здесь мы поговорим про нахождение наименьшего общего кратного (НОК), и особое внимание уделим решению примеров. Сначала покажем, как вычисляется НОК двух чисел через НОД этих чисел. Дальше рассмотрим нахождение наименьшего общего кратного с помощью разложения чисел на простые множители. После этого остановимся на нахождении НОК трех и большего количества чисел, а также уделим внимание вычислению НОК отрицательных чисел.


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

Один из способов нахождения наименьшего общего кратного основан на связи между НОК и НОД. Существующая связь между НОК и НОД позволяет вычислять наименьшее общее кратное двух целых положительных чисел через известный наибольший общий делитель. Соответствующая формула имеет вид НОК(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.

Нахождение НОК трех и большего количества чисел

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

Теорема.

Пусть даны целые положительные числа a1, a2, …, ak, наименьшее общее кратное mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak).

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

Пример.

Найдите НОК четырех чисел 140, 9, 54 и 250.

Решение.

В этом примере a1=140, a2=9, a3=54, a4=250.

Сначала находим m2=НОК(a1, a2)=НОК(140, 9). Для этого по алгоритму Евклида определяем НОД(140, 9), имеем 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4, следовательно, НОД(140, 9)=1, откуда НОК(140, 9)=140·9:НОД(140, 9)=140·9:1=1 260. То есть, m2=1 260.

Теперь находим m3=НОК(m2, a3)=НОК(1 260, 54). Вычислим его через НОД(1 260, 54), который также определим по алгоритму Евклида: 1 260=54·23+18, 54=18·3. Тогда НОД(1 260, 54)=18, откуда НОК(1 260, 54)=1 260·54:НОД(1 260, 54)=1 260·54:18=3 780. То есть, m3=3 780.

Осталось найти m4=НОК(m3, a4)=НОК(3 780, 250). Для этого находим НОД(3 780, 250) по алгоритму Евклида: 3 780=250·15+30, 250=30·8+10, 30=10·3. Следовательно, НОД(3 780, 250)=10, откуда НОК(3 780, 250)=3 780·250:НОД(3 780, 250)=3 780·250:10=94 500. То есть, m4=94 500.

Таким образом, наименьшее общее кратное исходных четырех чисел равно 94 500.

Ответ:

НОК(140, 9, 54, 250)=94 500.

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

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

Пример.

Найдите наименьшее общее кратное пяти чисел 84, 6, 48, 7, 143.

Решение.

Сначала получаем разложения данных чисел на простые множители: 84=2·2·3·7, 6=2·3, 48=2·2·2·2·3, 7 (7простое число, оно совпадает со своим разложением на простые множители) и 143=11·13.

Для нахождения НОК данных чисел к множителям первого числа 84 (ими являются 2, 2, 3 и 7) нужно добавить недостающие множители из разложения второго числа 6. Разложение числа 6 не содержит недостающих множителей, так как и 2 и 3 уже присутствуют в разложении первого числа 84. Дальше к множителям 2, 2, 3 и 7 добавляем недостающие множители 2 и 2 из разложения третьего числа 48, получаем набор множителей 2, 2, 2, 2, 3 и 7. К этому набору на следующем шаге не придется добавлять множителей, так как 7 уже содержится в нем. Наконец, к множителям 2, 2, 2, 2, 3 и 7 добавляем недостающие множители 11 и 13 из разложения числа 143. Получаем произведение 2·2·2·2·3·7·11·13, которое равно 48 048.

Следовательно, НОК(84, 6, 48, 7, 143)=48 048.

Ответ:

НОК(84, 6, 48, 7, 143)=48 048.

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

Иногда встречаются задания, в которых требуется найти наименьшее общее кратное чисел, среди которых одно, несколько или все числа являются отрицательными. В этих случаях все отрицательные числа нужно заменить противоположными им числами, после чего находить НОК положительных чисел. В этом и состоит способ нахождения НОК отрицательных чисел. Например, НОК(54, −34)=НОК(54, 34), а НОК(−622, −46, −54, −888)=НОК(622, 46, 54, 888).

Мы можем так поступать, потому что множество кратных числа a совпадает со множеством кратных числа −a (a и −aпротивоположные числа). Действительно, пусть b – какое-то кратное числа a, тогда b делится на a, и понятие делимости утверждает существование такого целого числа q, что b=a·q. Но будет справедливо и равенство b=(−a)·(−q), которое в силу того же понятия делимости означает, что b делится на −a, то есть, b есть кратное числа −a. Справедливо и обратное утверждение: если b – какое-то кратное числа −a, то b является кратным и числа a.

Пример.

Найдите наименьшее общее кратное отрицательных чисел −145 и −45.

Решение.

Заменим отрицательные числа −145 и −45 на противоположные им числа 145 и 45. Имеем НОК(−145, −45)=НОК(145, 45). Определив НОД(145, 45)=5 (например, по алгоритму Евклида), вычисляем НОК(145, 45)=145·45:НОД(145, 45)=145·45:5=1 305. Таким образом, наименьшее общее кратное отрицательных целых чисел −145 и −45 равно 1 305.

Ответ:

НОК(−145, −45)=1 305.

Список литературы.

  • Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
  • Виноградов И.М. Основы теории чисел.
  • Михелович Ш.Х. Теория чисел.
  • Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.