Теория:
Пример:
имеются \(45\) апельсинов и \(60\) мандаринов. Найди наибольшее количество одинаковых наборов, которые можно собрать из этих фруктов.
Решая такую задачу, найдём все делители числа \(45\) и числа \(60\).
Для \(45\) это: \(1\); \(3\); \(5\); \(9\); \(15\); \(45\).
Для \(60\) это: \(1\); \(2\); \(3\); \(4\); \(5\); \(6\); \(10\); \(12\); \(15\); \(20\); \(30\), \(60\).
Общими делителями этих чисел будут: \(1\); \(3\); \(5\); \(15\).
Наибольшим является число \(15\).
Наибольшее натуральное число, на которое делятся без остатка числа \(m\) и \(n\), называют наибольшим общим делителем этих чисел.
Обозначают: \(НОД(m; n)\).
Так, в задаче \(НОД(45; 60) = 15\).
Наибольший общий делитель нескольких натуральных чисел можно найти, не выписывая все делители этих чисел.
Правило отыскания \(НОД\):
1. разложить данные числа на простые множители.
2. Выписать все простые числа, которые одновременно входят в каждое из полученных разложений.
3. Каждое из выписанных простых чисел взять с наименьшим из показателей степени, с которыми оно входит в разложения данных чисел.
4. Записать произведение полученных степеней.
Пример:
найдём \(НОД(20; 27)\).
Разложив на множители каждое из этих чисел, получим:
Значит, у данных чисел нет других общих множителей, кроме \(1\), т. е. число \(1\) — единственный общий делитель данных чисел.
\(НОД(20; 27) = 1\).
Натуральные числа называют взаимно простыми, если их наибольший общий делитель равен
\(1\).
Признак делимости на произведение взаимно простых чисел:
если число делится на каждое из взаимно простых чисел, то оно делится и на их произведение.
Пример:
число \(540\) делится как на \(20\), так и на \(27\). Значит, \(540\) будет делиться и на их произведение, т. е. .