НОД (наибольший общий делитель) — это максимальное число, на которое делятся несколько рассматриваемых чисел.
Теперь о том, как найти НОД двух чисел или более.
Алгоритм нахождения НОД
- Осуществите разложения на простые множители каждое из исследуемых чисел. Не забудьте указать степень над каждым простым множителем.
- Отдельной строкой в порядке возрастания выпишите простые множители, встречающиеся в разложении каждого из чисел с минимальной степенью, с которой этот множитель встречается во всех разложениях.
- Сосчитайте произведение выписанных в степенях чисел.
Следуя данному алгоритму, можно произвести определение НОД двух чисел и более. Наименьший же общий делитель всегда равен единице.
Возможны задачи, в которых НОД нужно найти через наибольшее общее кратное (НОК). Тогда формула нахождения НОД двух чисел или более выглядит так:
НОД(a;b)=a⋅bНОК(a;b).
Свойства НОД
- НОД двух чисел a и b делится на любой общий множитель;
- Если число a делится на b без остатка, то НОД(a;b)=b;
- При делении a и b на НОД получаются взаимно простые числа.
Осуществите каноническое разложение следующих чисел:
735;525;882;1925;156;208;495;693;247.
Чему равен НОД первых трёх чисел?
Решение:
735=3⋅5⋅5⋅72;
525=3⋅52⋅72;
882=2⋅32⋅72;
1925=52⋅7⋅11;
156=22⋅3⋅13;
208=24⋅13;
495=32⋅5⋅11;
693=32⋅7⋅11;
247=13⋅19.
Для того чтобы найти наибольший общий делитель для чисел 735;525;882, выпишем их общие множители с минимальными степенями:
НОД(735;525;882)=3⋅7=21.
