Нод двух чисел способы нахождения

Как найти НОД

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

Нахождение путём разложения на множители

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

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

Пример 1. Найти НОД (84, 90).

Решение: Раскладываем числа 84 и 90 на простые множители:

Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой:

Таким образом, НОД (84, 90) = 6.

Пример 2. Найти НОД (15, 28).

Решение: Раскладываем 15 и 28 на простые множители:

Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель — единица.

Алгоритм Евклида

Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.

Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.

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

Пример 1. Возьмём два числа 27 и 9. Так как 27 делится на 9 и 9 делится на 9, значит, 9 является общим делителем чисел 27 и 9. Этот делитель является в тоже время и наибольшим, потому что 9 не может делиться ни на какое число, большее 9. Следовательно:

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

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

Пример 2. Найдём наибольший общий делитель чисел 140 и 96:

1) 140 : 96 = 1 (остаток 44)

2) 96 : 44 = 2 (остаток 8)

3) 44 : 8 = 5 (остаток 4)

Последний делитель равен 4 — это значит:

Последовательное деление так же можно записывать столбиком:

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

1. Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
2. Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
3. Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.

Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа — 48:

48 делится на 4 без остатка. Таким образом:

Источник

Как найти НОД двух чисел по алгоритму Евклида

Что такое алгоритм Евклида

Алгоритм Евклида — один из наиболее ранних численных алгоритмов в истории. Название было дано в честь греческого математика Евклида, который впервые дал ему описание в книгах «Начала». Изначально назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль. Сегодня чаще используется взятие остатка от деления вместо вычитания, но суть метода сохранилась.

Алгоритм Евклида — это алгоритм, основная функция которого заключается в поиске наибольшего общего делителя (НОД) для двух целых чисел.

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

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

Понятие НОД

Аббревиатура НОД расшифровывается как «наибольший общий делитель».

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

Основная суть алгоритма Евклида

Суть алгоритма заключается в построении ряда следующего вида (при условии, что a больше b):

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

В нем каждое последующее число является результатом вычитания двух предыдущих, ряд заканчивается, когда частное становится равным 0 — при условии использования вычитания.

Последовательность нахождения НОД при помощи деления:

1. Большее число делится на меньшее.
2. Если результат деления:

• без остатка, то меньшее число и есть НОД;
• с остатком, тогда большее число заменяется на остаток.

1. Переход к пункту 1.

60 / 36 = 1 (остаток 24)

36 / 24 = 1 (остаток 12)

24 / 12 = 2 (остаток 0)

НОД для 60 и 36 равен 12 (делитель).

Последовательность нахождения НОД при помощи вычитания:

1. Из большего числа вычитается меньшее.
2. Если результат вычитания:

• равен 0, то числа равны друг другу и являются НОД;
• не равен 0, в таком случае большее число заменяется на результат вычитания.

1. Переход к пункту 1.

НОД для 60 и 36 равен 12 (уменьшаемое, вычитаемое)

Примеры решения задач с алгоритмом Евклида

Найти наибольший общий делитель для чисел 128 и 96.

128 / 96 = 1 (остаток 32)

Найти наибольший общий делитель для чисел 37 и 17.

37 / 17 = 2 (остаток 3)

17 / 3 = 5 (остаток 2)

3 / 2 = 1 (остаток 1)

2 / 1 = 2 (остаток 0)

Числа 37 и 17 являются простыми, соответственно, их НОД — единица. Совет: перед вычислениями проверяйте таблицу простых чисел.

Источник

НОД, НОД

НОД — это наибольший общий делитель.

НОК — это наименьшее общее кратное.

Определения:

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

Способы нахождения НОД двух чисел:

1 способ (следует из определения): Метод полного перебора для нахождения наибольшего общего делителя (НОД) натуральных чисел.

1. Выписываем все делители числа а;
2. Выписываем все делители числа b;
3. Выбираем среди них общие делители;
4. Среди общих делителей выбираем самое большое число – это и есть НОД(a, b).

2 способ : Метод перебора делителей меньшего числа для нахождения наибольшего общего делителя (НОД) натуральных чисел.

1. Найти делители меньшего из данных чисел.
2. Найти, начиная с большего, тот из выписанных делителей, который является также делителем другого числа.
3. Записать найденное число – НОД.

3 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители.

1. Находим разложение чисел на простые множители.
2. Подчеркиваем общие числа.
3. Находим произведение подчеркнутых чисел у одного числа.
4. Записываем ответ.

4 способ: Алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел вычитанием.

1. Из большего числа вычитается меньшее.
2. Если получается 0, то числа равны друг другу и являются наибольшим общим делителем.
3. Если результат вычитания не равен 0, то большее число заменяется на результат вычитания.
4. Переход к пункту 1.

Способы нахождения НОК двух чисел:

1 способ: Метод перебора
1. Выписываем в строчку кратные для каждого из чисел, пока не найдётся кратное, одинаковое для обоих чисел.

2 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители

1. Разложить данные числа на простые множители.
2. Выписать в строчку множители, входящие в разложение самого большого из чисел, а под ним — разложение остальных чисел.
3. Подчеркнуть в разложении меньшего числа множители, которые не вошли в разложение бóльшего числа и добавить эти множители в разложение большего числа.
4. Полученное произведение записать в ответ.

Свойства наибольшего общего делителя:

1. НОД(a, b) = НОД(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОД(a, 0) = |a|
5. НОД(a, к • a) = |a|, при любом к ∈ Z
6. НОД(a, НОД(b, с)) = НОД(НОД(a, b), c)

Свойства наименьшего общего кратного:

1. НОК(a, b) = НОК(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОК(a, НОК(b, с)) = НОК(НОК(a, b), c)

Источник

Нахождение НОД по алгоритму Евклида и с помощью разложения на простые множители.

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

Навигация по странице.

Алгоритм Евклида для нахождения НОД

В статье наибольший общий делитель (НОД), определение, примеры, свойства НОД мы сформулировали и доказали алгоритм Евклида. Алгоритм Евклида является универсальным способом, позволяющим вычислять наибольший общий делитель двух положительных целых чисел.

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

Деление заканчивается, когда r_k+1=0 , при этом r_k=НОД(a, b) .

Рассмотрим примеры нахождения НОД по алгоритму Евклида.

Найдите наибольший общий делитель чисел 64 и 48 .

Воспользуемся алгоритмом Евклида. В этом примере a=64 , b=48 .

Делим 64 на 48 , получаем 64:48=1 (ост. 16) (при необходимости смотрите правила и примеры деления с остатком), что можно записать в виде равенства 64=48·1+16 , то есть, q₁=1 , r₁=16 .

Теперь делим b на r₁ , то есть, 48 делим на 16 , получаем 48:16=3 , откуда имеем 48=16·3 . Здесь q₂=3 , а r₂=0 , так как 48 делится на 16 без остатка. Мы получили r₂=0 , поэтому это был последний шаг алгоритма Евклида, и r₁=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 .

Для закрепления материала найдем с помощью алгоритма Евклида наибольший общий делитель чисел 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 .

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

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

Приведем пример для пояснения правила нахождения НОД. Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5 . Общими простыми множителями, участвующими в разложении чисел 220 и 600 , являются 2 , 2 и 5 . Следовательно, НОД(220, 600)=2·2·5=20 .

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

Рассмотрим пример нахождения НОД по озвученному правилу.

Найдите наибольший общий делитель чисел 72 и 96 .

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

То есть, 72=2·2·2·3·3 и 96=2·2·2·2·2·3 . Общими простыми множителями являются 2 , 2 , 2 и 3 . Таким образом, НОД(72, 96)=2·2·2·3=24 .

В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что НОД(m·a₁, m·b₁)=m·НОД(a₁, b₁) , где m – любое целое положительное число.

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

Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a₁, a₂, …, a_k равен числу d_k , которое находится при последовательном вычислении НОД(a₁, a₂)=d₂ , НОД(d₂, a₃)=d₃ , НОД(d₃, a₄)=d₄ , …, НОД(d_k-1, a_k)=d_k .

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

Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .

Сначала по алгоритму Евклида определим наибольший общий делитель d₂ двух первых чисел 78 и 294 . При делении получаем равенства 294=78·3+60 ; 78=60·1+18 ; 60=18·3+6 и 18=6·3 . Таким образом, d₂=НОД(78, 294)=6 .

Теперь вычислим d₃=НОД(d₂, a₃)=НОД(6, 570) . Опять применим алгоритм Евклида: 570=6·95 , следовательно, d₃=НОД(6, 570)=6 .

Осталось вычислить d₄=НОД(d₃, a₄)=НОД(6, 36) . Так как 36 делится на 6 , то d₄=НОД(6, 36)=6 .

Таким образом, наибольший общий делитель четырех данных чисел равен d₄=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 .

Нахождение НОД отрицательных чисел

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

Найдите НОД отрицательных целых чисел −231 и −140 .

Модуль числа −231 равен 231 , а модуль числа −140 равен 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 равен 7 .

Определите НОД трех чисел −585 , 81 и −189 .

При нахождении наибольшего общего делителя отрицательные числа можно заменить их абсолютными величинами, то есть, НОД(−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)=3·3=9 , следовательно, НОД(−585, 81, −189)=9 .

Источник