Пусть даны числа 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 называется наибольшим общим делителем.
Для любых заданных натуральных чисел 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