2.8. Наибольший общий делитель. Взаимно простые числа

Общий делитель — число, которое является делителем каждого из данных чисел. Например, $4$ — общий делитель чисел $12$ и $20$. Число $1$ — общий делитель любых чисел.

Наибольший общий делитель (НОД) — наибольшее натуральное число, на которое делится без остатка каждое из данных чисел. Запись: НОД$(a, b)$.

Два способа нахождения НОД:

1. Перебор делителей. Выписываем все делители каждого числа, отмечаем общие и берём наибольший. Удобно для небольших чисел.

2. Разложение на простые множители. Раскладываем числа на простые множители, берём простые множители, общие для всех разложений, с наименьшим показателем степени и перемножаем их.

3. Если наименьшее из чисел является делителем каждого из остальных, то НОД равен этому наименьшему числу: НОД$(15, 45, 60) = 15$.

Взаимно простые числа — числа, у которых единственный общий делитель $1$, то есть НОД равен $1$. Например, $8$ и $15$ взаимно простые: оба составные, но общих простых множителей у них нет. Любые два соседних натуральных числа взаимно простые.

Пример 1: НОД$(24, 40)$. Д$(24) = \{1, 2, 3, 4, 6, 8, 12, 24\}$, Д. Общие: . НОД.

На рисунке в левом круге — делители $24$, в правом — делители $40$; в общей части — общие делители $1, 2, 4, 8$.

Пример 2: $120 = 2^3 \cdot 3 \cdot 5$, $180 = 2^2 \cdot 3^2 \cdot 5$. Общие множители: , , . НОД.

На рисунке простые множители чисел $120$ и $180$; произведение чисел $2, 2, 3, 5$ из общей части — НОД$(120, 180) = 60$.

Пример 3: $36$ яблок и $54$ груши раздают детям так, чтобы каждому досталось поровну яблок и поровну груш. Наибольшее число детей? Число детей — делитель и $36$, и $54$, а наибольшее — НОД$(36, 54) = 18$.

Частая ошибка: брать общие множители с наибольшим показателем или перемножать и необщие множители. НОД никогда не бывает больше наименьшего из данных чисел.