Question

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

Answer 1

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