Нахождение НОД по алгоритму Евклида и с помощью разложения на простые множители.
Эта статья про нахождение наибольшего общего делителя (НОД) двух и большего количества чисел. Сначала рассмотрим алгоритм Евклида, он позволяет находить НОД двух чисел. После этого остановимся на методе, позволяющем вычислять НОД чисел как произведение их общих простых множителей. Дальше разберемся с нахождением наибольшего общего делителя трех и большего количества чисел, а также приведем примеры вычисления НОД отрицательных чисел.
Алгоритм Евклида для нахождения НОД
В статье наибольший общий делитель (НОД), определение, примеры, свойства НОД мы сформулировали и доказали алгоритм Евклида. Алгоритм Евклида является универсальным способом, позволяющим вычислять наибольший общий делитель двух положительных целых чисел.
Напомним суть алгоритма Евклида. Для нахождения наибольшего общего делителя двух чисел 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.
Ответ:
НОД(64, 48)=16.
Покажем решение еще одного примера, но теперь обойдемся без подробных пояснений шагов алгоритма Евклида.
Пример.
Чему равен НОД чисел 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.
Ответ:
НОД(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.
Ответ:
НОД(72, 96)=24.
В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что НОД(m·a1, m·b1)=m·НОД(a1, b1), где m – любое целое положительное число.
Нахождение НОД трех и большего количества чисел
Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3, НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.
Давайте разберемся, как выглядит процесс нахождения НОД нескольких чисел, рассмотрев решение примера.
Пример.
Найдите наибольший общий делитель четырех чисел 78, 294, 570 и 36.
Решение.
В этом примере a1=78, a2=294, a3=570, a4=36.
Сначала по алгоритму Евклида определим наибольший общий делитель d2 двух первых чисел 78 и 294. При делении получаем равенства 294=78·3+60; 78=60·1+18; 60=18·3+6 и 18=6·3. Таким образом, d2=НОД(78, 294)=6.
Теперь вычислим d3=НОД(d2, a3)=НОД(6, 570). Опять применим алгоритм Евклида: 570=6·95, следовательно, d3=НОД(6, 570)=6.
Осталось вычислить d4=НОД(d3, a4)=НОД(6, 36). Так как 36 делится на 6, то d4=НОД(6, 36)=6.
Таким образом, наибольший общий делитель четырех данных чисел равен d4=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.
Ответ:
НОД(−231, −140)=7.
Пример.
Определите НОД трех чисел −585, 81 и −189.
Решение.
При нахождении наибольшего общего делителя отрицательные числа можно заменить их абсолютными величинами, то есть, НОД(−585, 81, −189)=
Ответ:
НОД(−585, 81, −189)=9.
Список литературы.
- Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
- Виноградов И.М. Основы теории чисел.
- Михелович Ш.Х. Теория чисел.
- Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.