Почему нахождение наибольшего общего делителя важно при определении взаимной простоты чисел?

Нахождение наибольшего общего делителя (НОД) важно при определении взаимной простоты чисел, потому что НОД помогает доказать или опровергнуть взаимную простоту. 4

Два целых числа считаются взаимно простыми, если их НОД равен единице. 3 Это означает, что у чисел нет общих делителей, кроме единицы. 3 Если же НОД больше единицы, то числа не являются взаимно простыми. 4

Например, числа 45 и 500 не являются взаимно простыми, так как помимо единицы, у них есть ещё один общий делитель — 5, и он больше единицы. 4