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

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

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