Как найти наименьшее общее кратное? Делители и кратные числа.

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

Калькулятор для нахождения НОД и НОК

Найти НОД и НОК

Найдено НОД и НОК: 5806

Как пользоваться калькулятором

Введите числа в поле для ввода
В случае ввода некорректных символов поле для ввода будет подсвечено красным
нажмите кнопку "Найти НОД и НОК"

Как вводить числа

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

Что такое НОД и НОК?

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

Как проверить, что число делится на другое число без остатка?

Чтобы узнать, делится ли одно число на другое без остатка, можно воспользоваться некоторыми свойствами делимости чисел. Тогда, комбинируя их, можно проверять делимость на некоторые их них и их комбинации.

Некоторые признаки делимости чисел

1. Признак делимости числа на 2
Чтобы определить, делится ли число на два (является ли оно чётным), достаточно посмотреть на последнююю цифру этого числа: если она равна 0, 2, 4, 6 или 8, то число чётно, а значит делится на 2.
Пример: определить, делится ли на 2 число 34938 .
Решение: смотрим на последнюю цифру: 8 - значит число делится на два.

2. Признак делимости числа на 3
Число делится на 3 тогда, когда сумма его цифр делится на три. Таким образом, чтобы определить, делится ли число на 3, нужно посчитать сумму цифр и проверить, делится ли она на 3. Даже если сумма цифр получилась очень большой, можно повторить этот же процесс вновь.
Пример: определить, делится ли число 34938 на 3.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 3, а значит и число делится на три.

3. Признак делимости числа на 5
Число делится на 5 тогда, когда его последняя цифра равна нулю или пяти.
Пример: определить, делится ли число 34938 на 5.
Решение: смотрим на последнюю цифру: 8 - значит число НЕ делится на пять.

4. Признак делимости числа на 9
Этот признак очень похож на признак делимости на тройку: число делится на 9 тогда, когда сумма его цифр делится на 9.
Пример: определить, делится ли число 34938 на 9.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 9, а значит и число делится на девять.

Как найти НОД и НОК двух чисел

Как найти НОД двух чисел

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

Рассмотрим этот способ на примере нахождения НОД(28, 36) :

Раскладываем оба числа на множители: 28 = 1·2·2·7 , 36 = 1·2·2·3·3
Находим общие множители, то есть те, которые есть у обоих чисел: 1, 2 и 2.
Вычисляем произведение этих множителей: 1·2·2 = 4 - это и есть наибольший общий делитель чисел 28 и 36.

Как найти НОК двух чисел

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

Для вычисления НОК нужно вычислить произведение исходных чисел и затем разделить его на предварительно найденный НОД. Найдём НОК для тех же чисел 28 и 36:

Находим произведение чисел 28 и 36: 28·36 = 1008
НОД(28, 36), как уже известно, равен 4
НОК(28, 36) = 1008 / 4 = 252 .

Нахождение НОД и НОК для нескольких чисел

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

Аналогичное соотношение действует и для наименьшего общего кратного чисел: НОК(a, b, c) = НОК(НОК(a, b), c)

Пример: найти НОД и НОК для чисел 12, 32 и 36.

Cперва разложим числа на множители: 12 = 1·2·2·3 , 32 = 1·2·2·2·2·2 , 36 = 1·2·2·3·3 .
Найдём обшие множители: 1, 2 и 2 .
Их произведение даст НОД: 1·2·2 = 4
Найдём теперь НОК: для этого найдём сначала НОК(12, 32): 12·32 / 4 = 96 .
Чтобы найти НОК всех трёх чисел, нужно найти НОД(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , НОД = 1·2·2·3 = 12 .
НОК(12, 32, 36) = 96·36 / 12 = 288 .

Рассмотрим решение следующей задачи. Шаг мальчика составляет 75 см, а шаг девочки 60 см. Необходимо найти наименьшее расстояние, на котором они оба сделают по целому числу шагов.

Решение. Весь путь который пройдут ребята, должен делиться без остатка на 60 и на 70, так как они должны сделать каждый целое число шагов. Другими словами, в ответе должно быть число, кратное как 75 так и 60.

Сначала будем выписывать все кратные числа, для числа 75. Получаем:

75, 150, 225, 300, 375, 450, 525, 600, 675, … .

Теперь выпишем числа, которые будут кратны 60. Получаем:

60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, … .

Теперь находим числа которые есть в обоих рядах.

Общими кратными чисел будут числа, 300, 600, и т.д.

Самое наименьшее из них, это число 300. Оно в данном случае будет называться наименьшим общим кратным чисел 75 и 60.

Возвращаясь к условию задачи, наименьшее расстояние, на котором ребята сделают целое число шагов будет 300 см. Мальчик пройдет этот путь за 4 шага, а девочке потребуется сделать 5 шагов.

Определение наименьшего общего кратного

Наименьшим общим кратным двух натуральных чисел a и b называется наименьшее натуральное число, которое кратно как a, так и b.

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

Можно воспользоваться следующим методом.

Как найти наименьшее общее кратное

Сначала необходимо разложить данные числа на простые множители.

60 = 2*2*3*5,
75=3*5*5.

Теперь выпишем все множители которые есть в разложении первого числа (2,2,3,5) и добавим к нему все недостающие множители из разложения второго числа (5).

Получим в итоге ряд простых чисел: 2,2,3,5,5. Произведение этих чисел и будет наименьшим общим сомножителем для данных чисел. 2*2*3*5*5 = 300.

Общая схема нахождения наименьшего общего кратного

1. Разложить числа на простые множители.
2. Выписать простые множители которые входят в состав одного из них.
3. Добавить к этим множителям все те, которые есть в разложении остальных, но нет в выбранном.
4. Найти произведение всех выписанных сомножителей.

Данный способ универсален. С его помощью можно найти наименьшее общее кратное любого количества натуральных чисел.

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

Теорема.

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

Доказательство.

Пусть М – какое-нибудь кратное чисел a и b . То есть, М делится на a , и по определению делимости существует некоторое целое число k такое, что справедливо равенство M=a·k . Но М делится и на b , тогда a·k делится на b .

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

Также нужно записать два важных следствия из рассмотренной теоремы.

Общие кратные двух чисел совпадают с кратными их наименьшего общего кратного.

Это действительно так, так как любое общее кратное M чисел a и b определяется равенством M=НОК(a, b)·t при некотором целом значении t .

Наименьшее общее кратное взаимно простых положительных чисел a и b равно их произведению.

Обоснование этого факта достаточно очевидно. Так как a и b взаимно простые, то НОД(a, b)=1 , следовательно, НОК(a, b)=a·b:НОД(a, b)=a·b:1=a·b .

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

Нахождение наименьшего общего кратного трех и большего количества чисел можно свести к последовательному нахождению НОК двух чисел. Как это делается, указано в следующей теореме.a 1 , a 2 , …, a k совпадают с общими кратными чисел m k-1 и a k , следовательно, совпадают с кратными числа m k . А так как наименьшим положительным кратным числа m k является само число m k , то наименьшим общим кратным чисел a 1 , a 2 , …, a k является m k .

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

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

Второе число: b=

Разделитель разрядов Без разделителя пробел " ´

Результат:

Наибольший общий делитель НОД(a ,b )=6

Наименьшее общее кратное НОК(a ,b )=468

Наибольшее натуральное число, на которое делятся без остатка числа a и b, называется наибольшим общим делителем (НОД) этих чисел. Обозначается НОД(a,b), (a,b), gcd(a,b) или hcf(a,b).

Наименьшее общее кратное (НОК) двух целых чисел a и b есть наименьшее натуральное число, которое делится на a и b без остатка. Обозначается НОК(a,b), или lcm(a,b).

Целые числа a и b называются взаимно простыми , если они не имеют никаких общих делителей кроме +1 и −1.

Наибольший общий делитель

Пусть даны два положительных числа a 1 и a 2 1). Требуется найти общий делитель этих чисел, т.е. найти такое число λ , которое делит числа a 1 и a 2 одновременно. Опишем алгоритм.

1) В данной статье под словом число будем понимать целое число.

Пусть a 1 ≥ a 2 , и пусть

где m 1 , a 3 некоторые целые числа, a 3 <a 2 (остаток от деления a 1 на a 2 должен быть меньше a 2).

Предположим, что λ делит a 1 и a 2 , тогда λ делит m 1 a 2 и λ делит a 1 −m 1 a 2 =a 3 (Утверждение 2 статьи "Делимость чисел. Признак делимости"). Отсюда следует, что всякий общий делитель a 1 и a 2 является общим делителем a 2 и a 3 . Справедливо и обратное, если λ общий делитель a 2 и a 3 , то m 1 a 2 и a 1 =m 1 a 2 +a 3 также делятся на λ . Следовательно общий делитель a 2 и a 3 есть также общий делитель a 1 и a 2 . Так как a 3 <a 2 ≤a 1 , то можно сказать, что решение задачи по нахождению общего делителя чисел a 1 и a 2 сведено к более простой задаче нахождения общего делителя чисел a 2 и a 3 .

Если a 3 ≠0, то можно разделить a 2 на a 3 . Тогда

где m 1 и a 4 некоторые целые числа, (a 4 остаток от деления a 2 на a 3 (a 4 <a 3)). Аналогичными рассуждениями мы приходим к выводу, что общие делители чисел a 3 и a 4 совпадают с общими делителями чисел a 2 и a 3 , и также с общими делителями a 1 и a 2 . Так как a 1 , a 2 , a 3 , a 4 , ... числа, постоянно убывающие, и так как существует конечное число целых чисел между a 2 и 0, то на каком то шаге n , остаток от деления a n на a n+1 будет равен нулю (a n+2 =0).

Каждый общий делитель λ чисел a 1 и a 2 также делитель чисел a 2 и a 3 , a 3 и a 4 , .... a n и a n+1 . Справедливо и обратное, общие делители чисел a n и a n+1 являются также делителями чисел a n−1 и a n , .... , a 2 и a 3 , a 1 и a 2 . Но общий делитель чисел a n и a n+1 является число a n+1 , т.к. a n и a n+1 без остатка делятся на a n+1 (вспомним, что a n+2 =0). Следовательно a n+1 является и делителем чисел a 1 и a 2 .

Отметим, что число a n+1 является наибольшим из делителей чисел a n и a n+1 , так как наибольший делитель a n+1 является сам a n+1 . Если a n+1 можно представить в виде произведения целых чисел, то эти числа также являются общими делителями чисел a 1 и a 2 . Число a n+1 называют наибольшим общим делителем чисел a 1 и a 2 .

Числа a 1 и a 2 могут быть как положительными, так и отрицательными числами. Если один из чисел равен нулю, то наибольший общий делитель этих чисел будет равен абсолютной величине другого числа. Наибольший общий делитель нулевых чисел не определен.

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

Пример нахождения наибольшего общего делителя двух чисел

Найти наибольший общий делитель двух чисел 630 и 434.

Шаг 1. Делим число 630 на 434. Остаток 196.
Шаг 2. Делим число 434 на 196. Остаток 42.
Шаг 3. Делим число 196 на 42. Остаток 28.
Шаг 4. Делим число 42 на 28. Остаток 14.
Шаг 5. Делим число 28 на 14. Остаток 0.

На шаге 5 остаток от деления равен 0. Следовательно наибольший общий делитель чисел 630 и 434 равен 14. Заметим, что числа 2 и 7 также являются делителями чисел 630 и 434.

Взаимно простые числа

Определение 1. Пусть наибольший общий делитель чисел a 1 и a 2 равен единице. Тогда эти числа называются взаимно простыми числами , не имеющими общего делителя.

Теорема 1. Если a 1 и a 2 взаимно простые числа, а λ какое то число, то любой общий делитель чисел λa 1 и a 2 является также общим делителем чисел λ и a 2 .

Доказательство. Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя чисел a 1 и a 2 (см. выше).

Из условия теоремы следует, что наибольшим общим делителем чисел a 1 и a 2 , и следовательно a n и a n+1 является 1. Т.е. a n+1 =1.

Умножим все эти равенства на λ , тогда

Пусть общий делитель a 1 λ и a 2 есть δ . Тогда δ входит множителем в a 1 λ , m 1 a 2 λ и в a 1 λ -m 1 a 2 λ =a 3 λ (см. "Делимость чисел",Утверждение 2). Далее δ входит множителем в a 2 λ и m 2 a 3 λ , и, следовательно, входит множителем в a 2 λ -m 2 a 3 λ =a 4 λ .

Рассуждая так мы убеждаемся, что δ входит множителем в a n−1 λ и m n−1 a n λ , и, следовательно, в a n−1 λ −m n−1 a n λ =a n+1 λ . Так как a n+1 =1, то δ входит множителем в λ . Следовательно число δ является общим делителем чисел λ и a 2 .

Рассмотрим частные случаи теоремы 1.

Следствие 1. Пусть a и c простые числа относительно b . Тогда их произведение ac является простым числом относительно b .

Действительно. Из теоремы 1 ac и b имеют тех же общих делителей, что и c и b . Но числа c и b взаимно простые, т.е. имеют единственный общий делитель 1. Тогда ac и b также имеют единственный общий делитель 1. Следовательно ac и b взаимно простые.

Следствие 2. Пусть a и b взаимно простые числа и пусть b делит ak . Тогда b делит и k .

Действительно. Из условия утверждения ak и b имеют общий делитель b . В силу теоремы 1, b должен быть общим делителем b и k . Следовательно b делит k .

Следствие 1 можно обобщить.

Следствие 3. 1. Пусть числа a 1 , a 2 , a 3 , ..., a m простые относительно числа b . Тогда a 1 a 2 , a 1 a 2 ·a 3 , ..., a 1 a 2 a 3 ···a m , произведение этих чисел простое относительно числа b .

2. Пусть имеем два ряда чисел

таких, что каждое число первого ряда простое по отношению каждого числа второго ряда. Тогда произведение

Требуется найти такие числа, которые делятся на каждое из этих чисел.

Если число делится на a 1 , то оно имеет вид sa 1 , где s какое-нибудь число. Если q есть наибольший общий делитель чисел a 1 и a 2 , то

где s 1 - некоторое целое число. Тогда

является наименьшим общим кратным чисел a 1 и a 2 .

a 1 и a 2 взаимно простые, то наименьшее общее кратное чисел a 1 и a 2:

Нужно найти наименьшее общее кратное этих чисел.

Из вышеизложенного следует, что любое кратное чисел a 1 , a 2 , a 3 должно быть кратным чисел ε и a 3 , и обратно. Пусть наименьшее общее кратное чисел ε и a 3 есть ε 1 . Далее, кратное чисел a 1 , a 2 , a 3 , a 4 должно быть кратным чисел ε 1 и a 4 . Пусть наименьшее общее кратное чисел ε 1 и a 4 есть ε 2 . Таким образом выяснили, что все кратные чисел a 1 , a 2 , a 3 ,...,a m совпадают с кратными некоторого определенного числа ε n , которое называют наименьшим общим кратным данных чисел.

В частном случае, когда числа a 1 , a 2 , a 3 ,...,a m взаимно простые, то наименьшее общее кратное чисел a 1 , a 2 как было показано выше имеет вид (3). Далее, так как a 3 простое по отношению к числам a 1 , a 2 , тогда a 3 простое по отношению числа a 1 ·a 2 (Следствие 1). Значит наименьшее общее кратное чисел a 1 ,a 2 ,a 3 является число a 1 · a 2 ·a 3 . Рассуждая аналогичным образом мы приходим к следующим утверждениям.

Утверждение 1. Наименьшее общее кратное взаимно простых чисел a 1 , a 2 , a 3 ,...,a m равен их произведению a 1 ·a 2 ·a 3 ···a m .

Утверждение 2. Любое число, которое делится на каждое из взаимно простых чисел a 1 , a 2 , a 3 ,...,a m делится также на их произведение a 1 ·a 2 ·a 3 ···a m .

Общие кратные

Проще говоря, любое целое число, которое делится на каждое из данных чисел, является общим кратным данных целых чисел.

Можно находить общее кратное двух и большего количества целых чисел.

Пример 1

Вычислить общее кратное двух чисел: $2$ и $5$.

Решение .

По определению общим кратным чисел $2$ и $5$ является число $10$, т.к. оно кратно числу $2$ и числу $5$:

Общими кратными чисел $2$ и $5$ также будут числа $–10, 20, –20, 30, –30$ и т.д., т.к. все они делятся на числа $2$ и $5$.

Замечание 1

Нуль является общим кратным любого количества ненулевых целых чисел.

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

Для заданных целых чисел всегда можно найти их общее кратное.

Пример 2

Вычислить общее кратное чисел $111$ и $55$.

Решение .

Перемножим заданные числа: $111\div 55=6105$. Несложно убедится, что число $6105$ делится на число $111$ и на число $55$:

$6105\div 111=55$;

$6105\div 55=111$.

Таким образом, число $6105$ – общее кратное чисел $111$ и $55$.

Ответ : общее кратное чисел $111$ и $55$ равно $6105$.

Но, как мы уже видели из предыдущего примера, это общее кратное не одно. Другими общими кратными будут числа $–6105, 12210, –12210, 61050, –61050$ и т.д. Таким образом, мы пришли к следующему выводу:

Замечание 2

Любой набор целых чисел имеет бесконечное множество общих кратных.

На практике ограничиваются нахождением общих кратных только целых положительных (натуральных) чисел, т.к. множества кратных данного числа и ему противоположного совпадают.

Определение наименьшего общего кратного

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

Определение 2

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

Пример 3

Вычислить НОК чисел $4$ и $7$.

Решение .

Т.к. у данных чисел нет общих делителей, то $НОК(4,7)=28$.

Ответ : $НОК (4,7)=28$.

Нахождение НОК через НОД

Т.к. существует связь между НОК и НОД, с ее помощью можно вычислить НОК двух целых положительных чисел :

Замечание 3

Пример 4

Вычислить НОК чисел $232$ и $84$.

Решение .

Воспользуемся формулой для нахождения НОК через НОД:

$НОК (a,b)=\frac{a\cdot b}{НОД (a,b)}$

Найдем НОД чисел $232$ и $84$ с помощью алгоритма Эвклида:

$232=84\cdot 2+64$,

$84=64\cdot 1+20$,

$64=20\cdot 3+4$,

Т.е. $НОД (232, 84)=4$.

Найдем $НОК (232, 84)$:

$НОК (232,84)=\frac{232\cdot 84}{4}=58\cdot 84=4872$

Ответ : $НОК (232,84)=4872$.

Пример 5

Вычислить $НОК (23, 46)$.

Решение .

Т.к. $46$ делится нацело на $23$, то $НОД (23, 46)=23$. Найдем НОК:

$НОК (23,46)=\frac{23\cdot 46}{23}=46$

Ответ : $НОК (23,46)=46$.

Таким образом, можно сформулировать правило :

Замечание 4