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

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

Решение.

В этом примере a₁=78, a₂=294, a₃=570, a₄=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.

Ответ:

НОД(−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.

Ответ:

НОД(−585, 81, −189)=9.

35. Корені многочлена. Теорема Безу. (33 и выше)

36. Кратні корені, критерій кратності кореня.