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