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

Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители. Сформулируем правило: НОД двух целых положительных чисел 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·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.

Решение.

В этом примере 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.

К началу страницы