Наибольший общий делитель (НОД): как найти. Взаимно простые числа

Начнём с простого. 12 конфет можно раздать поровну 1, 2, 3, 4, 6 или 12 друзьям — и никто не обидится, остатка не будет. Эти числа и называются делителями.

Делитель числа $a$ — это число $d$, на которое $a$ делится без остатка. То есть $a=d\cdot k$, где $k$ — тоже какое-то натуральное число.

Смотри:

• Делители числа 12: это 1, 2, 3, 4, 6, 12.
• Делители числа 18: это 1, 2, 3, 6, 9, 18.

А теперь найди числа, которые есть в ОБОИХ списках. Это 1, 2, 3 и 6. Они называются общими делителями чисел 12 и 18 — на каждое из них делится и 12, и 18.

Кстати, заметь: единица делит вообще любое число. Поэтому у любых двух чисел точно есть хотя бы один общий делитель — единица. А раз общие делители есть всегда, среди них всегда найдётся самый большой. Вот он-то нам и нужен!

Для 12 и 18 общие делители — это 1, 2, 3, 6. Самый большой из них — 6. Значит, $\text{НОД}(12,18)=6$.

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

Способ 2: разложение на простые множители. Это главный приём в 6 классе:

1. Разложи каждое число на простые множители.
2. Выбери только те простые множители, которые есть в обоих разложениях. Каждый бери в наименьшей степени (то есть столько раз, сколько он встречается в том разложении, где его меньше).
3. Перемножь то, что выбрал, — это и есть НОД.

Если общих простых множителей нет совсем — значит, $\text{НОД}(a,b)=1$.

Проверь себя: НОД никогда не бывает больше меньшего из чисел. Если у тебя получился НОД(12, 18) = 36 — где-то закралась ошибка!

Бывает, что у двух чисел вообще нет общих делителей, кроме единицы. Такие числа — как соседи, у которых нет ничего общего.

Важная хитрость: взаимно простые числа НЕ обязаны сами быть простыми! Возьми 8 и 9. Оба составные: $8=2^3$, а $9=3^2$. Но общих простых множителей у них нет (у восьмёрки только двойки, у девятки только тройки), поэтому $\text{НОД}(8,9)=1$ — они взаимно простые.

Полезные факты:

• Два соседних числа $n$ и $n+1$ всегда взаимно просты. Например, 15 и 16, 99 и 100. Всегда!
• Простое число взаимно просто с любым числом, которое на него не делится.

Зачем это дробям? Дробь $\frac{a}{b}$ нельзя сократить ровно тогда, когда $\text{НОД}(a,b)=1$. Хочешь сократить дробь до конца за один шаг? Раздели числитель и знаменатель на их НОД — и готово.

Вот несколько свойств, которые экономят время:

1. Порядок не важен: $\text{НОД}(a,b)=\text{НОД}(b,a)$.
2. Если $a$ делится на $b$, то $\text{НОД}(a,b)=b$. Например, $\text{НОД}(20,10)=10$ — даже считать ничего не надо!
3. С единицей всё просто: $\text{НОД}(a,1)=1$ для любого $a$.
4. НОД сам делит оба числа, а любой другой общий делитель этих чисел делит НОД.

А если чисел три или больше? Находи НОД по цепочке, парами: $\text{НОД}(a,b,c)=\text{НОД}(\text{НОД}(a,b),c)$ Пример: ищем $\text{НОД}(12,18,30)$. Сначала $\text{НОД}(12,18)=6$, потом $\text{НОД}(6,30)=6$. Ответ: 6.

А можно и сразу через разложения: бери простые множители, которые есть во всех разложениях, каждый в наименьшей степени.

Есть способ найти НОД вообще без разложения на множители — ему больше 2000 лет, и придумал его древнегреческий математик Евклид. Работает он на одном свойстве: $\text{НОД}(a,b)=\text{НОД}(b,r)$, где $r$ — остаток от деления $a$ на $b$.

• Остаток ноль? Отлично, НОД — это меньшее число.
• Остаток не ноль? Тогда делитель становится новым делимым, остаток — новым делителем. И повторяй.

Пример: найдём $\text{НОД}(48,36)$. $48=36\cdot 1+12$ Остаток 12, продолжаем: $36=12\cdot 3+0$ Остаток ноль — стоп! $\text{НОД}(48,36)=12$.

Этот способ — настоящая палочка-выручалочка для больших чисел, когда раскладывать на простые множители слишком долго.