#14 Наибольший общий делитель

Общим делителем нескольких чисел называется число, служащее делителем для каждого из них. Например, числа $12$, $18$, $30$ имеют общий делитель $3$; число $2$ - тоже их общий делитель. Среди всех общих делителей всегда имеется наибольший, в нашем примере - число $6$. Это число называется наибольшим общим делителем (НОД).

Примеры. Для чисел $16$, $20$, $28$ НОД есть $4$; для чисел $5$, $30$, $60$, $90$ НОД есть $5$.
Когда числа небольшие, их НОД легко находится $110$ догадке. Если мы имеем дело с большим и числами, разлагаем каждое на простые множители (см. параграф $13$ ) и записываем те из них, которые входят во все данные числа. Каждый из таких множителей берем с на­именьшим показателем, с которым он входит в данные числа. Производим умножение.

Пример 1. Найти НОД чисел $252$, $441$, $1080$.
Разлагаем на простые множители
$$
252 = 2^2 \cdot 3^2 \cdot 7; \ 441 = 3^2 \cdot 7^2; \ 1080 = 2^3 \cdot 3^2 \cdot 5.
$$

Общим для чисел является только простой множи­тель $3$; наименьший из показателей, с которыми он входит в данные числа, есть $2$. НОД равен $32 = 9$.

Пример $2$. Найти НОД чисел $234$, $1080$, $8100$.
$$
234 = 2 \cdot 3^2 \cdot 13; 1080 = 2^3 \cdot 3^2 \cdot 5; 8100 = 2^2 \cdot 3^4 \cdot 5^2,
$$
$$
НОД = 2 \cdot 3^2 = 18.
$$
Может случиться так, что простых множителей, общих для всех данных чисел, не будет вовсе.
Тогда наибольший общий делитель есть $1$. Например, для чисел $15 = 3 \cdot 5, 10 = 2 \cdot 5, 6 = 2 \cdot 3 $ НОД = $1$. Два числа, НОД которых равен $1$, называются взаимно простыми. Например, $15$ и $22$ - взаимно простые числа.