Нахождение НОД и НОК чисел
Онлайн-калькулятор «Нахождение НОД и НОК чисел«. Наш калькулятор поможет вам найти наибольший общий делить (НОД) и наименьшее общее кратное (НОК) чисел. Особенностью данного калькулятора является то, что он может находить НОК и НОД не только двух чисел, но и трех или четырех чисел. Введите натуральные числа и нажмите кнопку «Вычислить» и наш калькулятор не просто выдаст ответ, но и представит подробное решение, где последовательно будет изложен порядок нахождения НОД и НОК чисел.
| Первое число | Второе число |
Наибольший общий делитель нескольких чисел – это наибольшее натуральное целое число, на которое эти числа делятся без остатка. Наибольший общий делитель обозначается следующим образом: НОД (18; 48) = 6
Наименьшее общее кратно нескольких чисел – это самое меньшее число, которое делится на каждое из этих чисел без остатка. Например: НОК (18; 48) = 144
Это следует знать! Как определить, что число делится на 3 без остатка? Очень просто – на 3 делятся только те числа, сумма цифр которых делится на 3. Например: число 795 делится на 3, так как сумма его цифр 7 + 9 + 5 = 21 делится на 3.
21 : 3 = 7
Нахождение НОД по алгоритму Евклида и с помощью разложения на простые множители
Рассмотрим два основных метода нахождения НОД двумя основными способами: с использованием алгоритма Евклида и путем разложения на простые множители. Применим оба метода для двух, трех и большего количества чисел.
Алгоритм Евклида для нахождения НОД
Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Формулировки и доказательство алгоритма Евклида мы привели в разделе «Наибольший общий делитель: определитель, примеры».
Суть алгоритма заключается в том, чтобы последовательно проводить деление с остатком, в ходе которого получается ряд равенств вида:
a = b · q 1 + r 1 , 0 < r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k — 2 = r k — 1 · q k + r k , 0 < r k < r k — 1 r k — 1 = r k · q k + 1
Мы можем закончить деление тогда, когда r k + 1 = 0 , при этом r k = НОД ( a , b ) .
Найдите наибольший общий делитель чисел 64 и 48 .
Решение
Введем обозначения: a = 64 , b = 48 .
На основе алгоритма Евклида проведем деление 64 на 48 .
Получим 1 и остаток 16 . Получается, что q 1 = 1 , r 1 = 16 .
Вторым шагом разделим 48 на 16 , получим 3 . То есть q 2 = 3 , а r 2 = 0 . Таким образом число 16 – это наибольший общий делитель для чисел из условия.
Ответ: НОД ( 64 , 48 ) = 16 .
Чему равен НОД чисел 111 и 432 ?
Решение
Делим 432 на 111 . Согласно алгоритму Евклида получаем цепочку равенств 432 = 111 · 3 + 99 , 111 = 99 · 1 + 12 , 99 = 12 · 8 + 3 , 12 = 3 · 4 .
Таким образом, наибольший общий делитель чисел 111 и 432 – это 3 .
Ответ: НОД ( 111 , 432 ) = 3 .
Найдите наибольший общий делитель чисел 661 и 113 .
Решение
Проведем последовательно деление чисел и получим НОД ( 661 , 113 ) = 1 . Это значит, что 661 и 113 – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.
Ответ: НОД ( 661 , 113 ) = 1 .
Нахождение НОД с помощью разложения чисел на простые множители
Для того, чтобы найти наибольший общий делитель двух чисел методом разложения на множители, необходимо перемножить все простые множители, которые получаются при разложении этих двух чисел и являются для них общими.
Если мы разложим числа 220 и 600 на простые множители, то получим два произведения: 220 = 2 · 2 · 5 · 11 и 600 = 2 · 2 · 2 · 3 · 5 · 5 . Общими в этих двух произведениях будут множители 2 , 2 и 5 . Это значит, что НОД ( 220 , 600 ) = 2 · 2 · 5 = 20 .
Найдите наибольший общий делитель чисел 72 и 96 .
Решение
Найдем все простые множители чисел 72 и 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Общими для двух чисел простые множители: 2 , 2 , 2 и 3 . Это значит, что НОД ( 72 , 96 ) = 2 · 2 · 2 · 3 = 24 .
Ответ: НОД ( 72 , 96 ) = 24 .
Правило нахождения наибольшего общего делителя двух чисел основано на свойствах наибольшего общего делителя, согласно которому НОД ( m · a 1 , m · b 1 ) = m · НОД ( a 1 , b 1 ) , где m – любое целое положительное число.
Нахождение НОД трех и большего количества чисел
Независимо от количества чисел, для которых нам нужно найти НОД, мы будем действовать по одному и тому же алгоритму, который заключается в последовательном нахождении НОД двух чисел. Основан этот алгоритм на применении следующей теоремы: НОД нескольких чисел a 1 , a 2 , … , a k равен числу d k , которое находится при последовательном вычислении НОД ( a 1 , a 2 ) = d 2 , НОД ( d 2 , a 3 ) = d 3 , НОД ( d 3 , a 4 ) = d 4 , … , НОД ( d k — 1 , a k ) = d k .
Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .
Решение
Введем обозначения: a 1 = 78 , a 2 = 294 , a 3 = 570 , a 4 = 36 .
Начнем с того, что найдем НОД чисел 78 и 294 : d 2 = НОД ( 78 , 294 ) = 6 .
Теперь приступим к нахождению d 3 = НОД ( d 2 , a 3 ) = НОД ( 6 , 570 ) . Согласно алгоритму Евклида 570 = 6 · 95 . Это значит, что d 3 = НОД ( 6 , 570 ) = 6 .
Найдем d 4 = НОД ( d 3 , a 4 ) = НОД ( 6 , 36 ) . 36 делится на 6 без остатка. Это позволяет нам получить d 4 = НОД ( 6 , 36 ) = 6 .
d 4 = 6 , то есть, НОД ( 78 , 294 , 570 , 36 ) = 6 .
Ответ: НОД ( 78 , 294 , 570 , 36 ) = 6 .
А теперь давайте рассмотрим еще один способ вычисления НОД для тех и большего количества чисел. Мы можем найти НОД, перемножив все общие простые множители чисел.
Вычислите НОД чисел 78 , 294 , 570 и 36 .
Решение
Произведем разложение данных чисел на простые множители: 78 = 2 · 3 · 13 , 294 = 2 · 3 · 7 · 7 , 570 = 2 · 3 · 5 · 19 , 36 = 2 · 2 · 3 · 3 .
Для всех четырех чисел общими простыми множителями будут числа 2 и 3 .
Получается, что НОД ( 78 , 294 , 570 , 36 ) = 2 · 3 = 6 .
Ответ: НОД ( 78 , 294 , 570 , 36 ) = 6 .
Нахождение НОД отрицательных чисел
Если нам приходится иметь дело с отрицательными числами, то для нахождения наибольшего общего делителя мы можем воспользоваться модулями этих чисел. Мы можем так поступить, зная свойство чисел с противоположными знаками: числа n и — n имеют одинаковые делители.
Найдите НОД отрицательных целых чисел − 231 и − 140 .
Решение
Для выполнения вычислений возьмем модули чисел, данных в условии. Это будут числа 231 и 140 . Запишем это кратко: НОД ( − 231 , − 140 ) = НОД ( 231 , 140 ) . Теперь применим алгоритм Евклида для нахождения простых множителей двух чисел: 231 = 140 · 1 + 91 ; 140 = 91 · 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 · 1 + 7 и 42 = 7 · 6 . Получаем, что НОД ( 231 , 140 ) = 7 .
А так как НОД ( − 231 , − 140 ) = НОД ( 231 , 140 ) , то НОД чисел − 231 и − 140 равен 7 .
Ответ: НОД ( − 231 , − 140 ) = 7 .
Определите НОД трех чисел − 585 , 81 и − 189 .
Решение
Заменим отрицательные числа в приведенном перечне на их абсолютные величины, получим НОД ( − 585 , 81 , − 189 ) = НОД ( 585 , 81 , 189 ) . Затем разложим все данные числа на простые множители: 585 = 3 · 3 · 5 · 13 , 81 = 3 · 3 · 3 · 3 и 189 = 3 · 3 · 3 · 7 . Общими для трех чисел являются простые множители 3 и 3 . Получается , что НОД ( 585 , 81 , 189 ) = НОД ( − 585 , 81 , − 189 ) = 9 .
Наибольший общий делитель двух, трех и более чисел
Данный калькулятор предназначен для нахождения наибольшего общего делителя двух, трех и более чисел онлайн.
Делители числа n – это числа, на которые делится число n нацело, то есть без остатка. Натуральные числа могут иметь два, три и большее количество делителей. Число называется простым, если оно делится только на само себя и на единицу.
Несколько чисел могут иметь одинаковые делители, которые будут являться общими делителями. Если единица является единственным общим делителем чисел, то такие числа называются взаимно простыми.
Среди общих делителей чисел выделяют наибольший из них. Наибольший общий делитель (сокращенно НОД) двух, трех и более чисел – наибольшее число, на которое данные числа делятся без остатка. Наибольший общий делитель взаимно простых числе по определению равен единице.
Для тех пользователей, кого интересует вопрос, как находить наибольший общий делитель двух, трех и более чисел самостоятельно, представим последовательность решения данной задачи. Во-первых, необходимо разложить делители чисел на простые множители. Во-вторых, выделяются одинаковые простые множители данных чисел. В-третьих, необходимо перемножить найденные до этого одинаковые простые множители чисел. Найденное произведение одинаковых простых множителей будет являться наибольшим общим делителем натуральных чисел.
Чтобы быстро найти наибольший общий делитель чисел, необязательно самостоятельно проходить все этапы решения. Просто введите числа в соответствующие ячейки калькулятора и нажмите кнопку «Вычислить».
Нахождение нод по алгоритму Евклида и с помощью разложения на простые множители.
Эта статья про нахождение наибольшего общего делителя (НОД) двух и большего количества чисел. Сначала рассмотрим алгоритм Евклида, он позволяет находить НОД двух чисел. После этого остановимся на методе, позволяющем вычислять НОД чисел как произведение их общих простых множителей. Дальше разберемся с нахождением наибольшего общего делителя трех и большего количества чисел, а также приведем примеры вычисления НОД отрицательных чисел.
Навигация по странице.
Алгоритм Евклида для нахождения НОД.
Нахождение НОД с помощью разложения чисел на простые множители.
Нахождение НОД трех и большего количества чисел.
Нахождение НОД отрицательных чисел.
Алгоритм Евклида для нахождения нод
В статье наибольший общий делитель (НОД), определение, примеры, свойства НОД мы сформулировали и доказали алгоритм Евклида. Алгоритм Евклида является универсальным способом, позволяющим вычислять наибольший общий делитель двух положительных целых чисел.
Напомним суть алгоритма Евклида. Для нахождения наибольшего общего делителя двух чисел aи b (a и b – целые положительные числа, причем a больше или равно b) последовательно выполняется деление с остатком, которое дает ряд равенств видаДеление заканчивается, когда rk+1=0, при этом rk=НОД(a, b).
Рассмотрим примеры нахождения НОД по алгоритму Евклида.
Найдите наибольший общий делитель чисел 64 и 48.
Воспользуемся алгоритмом Евклида. В этом примере a=64, b=48.
Делим 64 на 48, получаем 64:48=1 (ост. 16) (при необходимости смотрите правила и примеры деления с остатком), что можно записать в виде равенства 64=48·1+16, то есть,q1=1, r1=16.
Теперь делим b на r1, то есть, 48 делим на 16, получаем 48:16=3, откуда имеем48=16·3. Здесь q2=3, а r2=0, так как 48 делится на 16 без остатка. Мы получили r2=0, поэтому это был последний шаг алгоритма Евклида, и r1=16 является искомым наибольшим общим делителем чисел 64 и 48.
Покажем решение еще одного примера, но теперь обойдемся без подробных пояснений шагов алгоритма Евклида.
Чему равен НОД чисел 111 и 432?
Из свойств наибольшего общего делителя мы знаем, что НОД(111, 432)=НОД(432, 111). Воспользуемся алгоритмом Евклида для нахождения НОД(432, 111).
Разделив 432 на 111, получаем равенство 432=111·3+99.
На следующем шаге делим 111 на 99, имеем 111=99·1+12.
Деление 99 на 12 дает равенство 99=12·8+3.
А 12 на 3 делится без остатка и 12=3·4. Поэтому это последний шаг алгоритма Евклида, и НОД(432, 111)=3, следовательно, и искомый наибольший общий делитель чисел 111 и432 равен 3.
НОД(111, 432)=3.
Для закрепления материала найдем с помощью алгоритма Евклида наибольший общий делитель чисел 661 и 113.
Найдите НОД(661, 113) по алгоритму Евклида.
Выполняем деление: 661=113·5+96; 113=96·1+17; 96=17·5+11; 17=11·1+6; 11=6·1+5;6=5·1+1, наконец, 5=1·5. Таким образом, НОД(661, 113)=1, то есть, 661 и 113 –взаимно простые числа.
Заметим, что если бы мы с самого начала обратились к таблице простых чисел, то выяснили бы, что числа 661 и 113 – простые, откуда можно было бы сразу сказать, что их наибольший общий делитель равен 1.