Наибольший общий делитель нескольких натуральных чисел

Пусть даны числа 48 и 60. Выпишем все делители числа 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. Также выпишем все делители числа 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. Среди выписанных чисел есть одинаковые: 1, 2, 3, 4, 6, 12. Все эти числа назывыаются общими делитьелями чисел 48 и 60, наибольшее среди них число 12 называется наибольшим общим делителем.
Замечание.Для того чтобы выписать все делители, надо узнать сколько их всего будет у даного числа. Для этого надо разложить число 48 на простые множители: $$ 48 = 2^4 \cdot 3$$ . Число делителей числа 48: $$ \left( {4 + 1} \right) \cdot \left( {1 + 1} \right) = 5 \cdot 2 = 10 $$ . Т.е. степень числа 2 плюс 1 умножить на степень числа 3 плюс 1.
Для любых заданных натуральных чисел a и b можно найти наибольший общий делитель. Он обозначается HOD(a,b) и читается: "HOD от a и b" . Например, HOD(a,b ) = HOD(48,60) = 12.
Взаимно простие числа. Если числа a и b таковы, что HOD(a,b) = 1, то такие числа называют зваимно простые.

Пример: Числа 26 и 35 являются взаимно простыми, хотя сами они составные. Так как $$ 26 = 2 \cdot 13$$ и $$35 = 5 \cdot 7 $$ , то HOD(26,35) = 1.

Чтобы найти наибольший общий делитель нескольких чисел, надо разложть их на простые множители, найти общие простые множители и вычислить произведение общих простых множителей, взяв каждый из них с наименьшим, из имеющихся, показателем.

Пример: $$ \quad \quad $$Найти HOD(56,84,96)

Решение:

$$ 56 = 2 \cdot 2 \cdot 2 \cdot 7 = 2^3 \cdot 7 $$

$$ 96 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 = 2^5 \cdot 3 $$

$$ 84 = 2 \cdot 2 \cdot 3 \cdot 7 = 2^2 \cdot 3 \cdot 7 $$

и тогда HOD(56,84,96) = $$ 2^2 $$ = 4