Наибольший общий делитель и наименьшее общее кратное

Наибольший общий делитель (НОД) — наибольшее натуральное число, на которое без остатка делятся два или несколько чисел. НОД используют для решения задач на делимость и равное распределение, а наименьшее общее кратное (НОК) помогает находить минимальное число, кратное нескольким данным числам.

Что такое НОД и чем он отличается от НОК

Определение наибольшего общего делителя

Делитель числа — это число, на которое данное число делится без остатка. Например, делители числа 12: 1, 2, 3, 4, 6 и 12.

Число 12 и число 18 имеют общие делители 1, 2, 3 и 6. Самый большой из них — 6, поэтому:

Итак, НОД двух или нескольких чисел — наибольший из чисел, на которые делится каждое из них.

Числа называют взаимно простыми, если их НОД равен 1. Например:

У любого ненулевого натурального числа есть делитель 1, поэтому НОД положительных чисел всегда существует и не меньше 1.

Определение наименьшего общего кратного

Кратное числа — это результат умножения числа на натуральное число. Например, кратные 6:

Общее кратное — число, которое делится без остатка сразу на несколько чисел. Для 6 и 8 такими числами являются 24, 48, 72 и другие. Наименьшее из них — 24:

Наименьшее общее кратное положительных чисел — наименьшее положительное число, которое кратно каждому из них.

Главное различие между НОД и НОК

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

Например, для чисел 12 и 18:

• общие делители: 1, 2, 3, 6, поэтому НОД равен 6;
• общие кратные: 36, 72, 108 и другие, поэтому НОК равен 36.

Можно запомнить различие так:

• НОД связан с делением чисел на одинаковые части;
• НОК связан с совпадением циклов, периодов или повторяющихся действий.

Как найти НОД двух чисел

Нахождение НОД перечислением делителей

Для небольших чисел НОД удобно находить непосредственным перечислением делителей.

Рассмотрим числа 24 и 36.

Делители 24:

Делители 36:

Совпадающие делители:

Наибольший из них — 12, значит:

Алгоритм действий:

1. Выписать делители первого числа.
2. Выписать делители второго числа.
3. Найти совпадающие значения.
4. Выбрать среди них наибольшее.

Этот способ понятен, но при больших числах список делителей может оказаться длинным. Тогда применяют разложение на множители или алгоритм Евклида.

Проверка результата делением

Чтобы проверить найденный НОД, нужно убедиться в двух фактах:

1. он делит каждое из данных чисел без остатка;
2. большего подходящего делителя для обоих чисел не существует.

Например, для чисел 24 и 36 предполагаемый НОД равен 12:

Оба деления выполняются без остатка. Если НОД был найден перечислением делителей, отсутствие большего значения уже следует из полного списка. При использовании другого способа можно дополнительно проверить делители результата и убедиться, что ни один больший делитель не подходит одновременно к обоим числам.

Самого факта, что число делит оба исходных числа, недостаточно: это доказывает, что оно подходит как общий делитель, но ещё не доказывает, что оно наибольшее.

Способы нахождения наибольшего общего делителя

Разложение чисел на простые множители

Простое число имеет ровно два натуральных делителя: 1 и само число. Разложение на множители — представление числа в виде произведения простых чисел.

Найдём НОД чисел 84 и 126:

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

Правило можно сформулировать так:

• выполнить разложение на множители для каждого числа;
• найти простые множители, которые встречаются в каждом разложении;
• выбрать для них наименьшие степени;
• перемножить выбранные множители.

Если совпадающих простых множителей нет, НОД равен 1.

Алгоритм Евклида

Алгоритм Евклида позволяет найти НОД с помощью последовательного деления с остатком. Он основан на свойстве:

где $r$ — остаток от деления $a$ на $b$, а $a>b>0$.

Процесс повторяют, пока остаток не станет равен нулю. Последний ненулевой остаток и есть НОД.

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

Как выбрать подходящий способ

Перечисление делителей удобно для небольших чисел и первого знакомства с понятием НОД.

Разложение на множители полезно, когда нужно одновременно найти НОД и НОК или показать структуру чисел.

Алгоритм Евклида обычно быстрее при работе с большими числами. Он также удобен в вычислениях, где важен последовательный и универсальный способ получения НОД.

Как работает алгоритм Евклида

Последовательность действий с остатками

Чтобы найти НОД двух положительных чисел, большее число делят на меньшее с остатком. Затем меньшее число делят на полученный остаток. Действия повторяют до тех пор, пока очередной остаток не станет равен нулю.

Схема выглядит так:

где:

• $a$ — делимое;
• $b$ — делитель;
• $q$ — частное;
• $r$ — остаток, причём $0\le r<b$.

Если $r=0$, то текущий делитель является НОД. Если $r\ne 0$, продолжают деление пары $b$ и $r$.

Почему это работает? Любой общий делитель чисел $a$ и $b$ одновременно является делителем их разности $a-bq=r$. Поэтому набор чисел, делящих и $a$, и $b$, совпадает с набором чисел, делящих $b$ и $r$.

Пример применения алгоритма Евклида

Найдём НОД чисел 252 и 198.

Делим большее число на меньшее:

Теперь делим 198 на 54:

Далее:

Последний шаг:

Последний ненулевой остаток равен 18, поэтому:

Проверка:

Оба числа делятся на 18 без остатка.

Свойства НОД

НОД взаимно простых и одинаковых чисел

Если два числа взаимно простые, их НОД равен 1:

Это означает, что у них нет общих делителей, кроме единицы.

Для одинаковых ненулевых чисел НОД равен самому числу:

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

Число 8 делит и 8, и 40, а больше 8 подходящего делителя быть не может, поскольку делитель числа 8 не может быть больше самого числа.

Связь НОД с делимостью, умножением и разностью чисел

Если число $d$ является общим делителем чисел $a$ и $b$, то оно является делителем любой их целой линейной комбинации:

где $m$ и $n$ — целые числа.

В частности, общий делитель $a$ и $b$ является делителем их разности:

Именно это свойство лежит в основе алгоритма Евклида.

Для любого натурального числа $k$ выполняется:

Например:

поэтому:

Если НОД двух чисел равен $d$, то после деления обоих чисел на $d$ получаются взаимно простые числа:

Особые случаи: НОД числа и нуля

Для ненулевого числа $a$ принято считать:

Если $a$ — натуральное число, это просто $a$. Причина в том, что любое ненулевое число делит 0, а числа, делящие одновременно $a$ и 0, совпадают с делителями $a$.

Например:

Пара $(0,0)$ является особым случаем. В школьной арифметике НОД двух нулей обычно считают неопределённым, поскольку у нуля нет наибольшего натурального делителя: каждое натуральное число делит 0.

Как найти НОК и связать его с НОД

Нахождение НОК разложением на простые множители

Чтобы найти НОК с помощью разложения на простые множители, нужно:

1. разложить данные числа;
2. взять все простые множители, которые встречаются хотя бы в одном разложении;
3. для каждого множителя выбрать наибольшую степень;
4. перемножить выбранные множители.

Найдём НОК чисел 84 и 126:

Берём:

• $2^2$, потому что это большая степень двойки;
• $3^2$, потому что это большая степень тройки;
• $7$.

Получаем:

В отличие от НОД, при нахождении НОК учитывают все простые множители из обоих разложений, а не только совпадающие.

Формула связи НОД и НОК для двух чисел

Для двух положительных чисел $a$ и $b$ выполняется формула:

Отсюда можно найти НОК:

Например, для чисел 24 и 36:

Тогда:

Проверим результат:

Значит, 72 действительно кратно обоим числам.

При вычислениях формулу удобнее применять так:

Так промежуточное произведение может быть меньше, а риск получить слишком большие числа — ниже.

Задачи на применение НОД и НОК

Задача на разбиение предметов или чисел на равные группы

Есть 24 красных и 36 синих карандашей. Нужно составить наибольшее число одинаковых наборов так, чтобы в каждом наборе было одинаковое количество красных и одинаковое количество синих карандашей, а все карандаши были использованы.

Число наборов должно быть делителем и 24, и 36. Чтобы наборов получилось как можно больше, найдите наибольший общий делитель чисел 24 и 36:

Значит, можно составить 12 одинаковых наборов.

В каждом наборе будет:

красных и

синих карандаша.

Ответ: 12 наборов; в каждом — 2 красных и 3 синих карандаша.

В задачах на разбиение предметов на максимально большое число одинаковых групп обычно используют НОД.

Задача на одновременное повторение событий

Один сигнал включается каждые 6 минут, а другой — каждые 8 минут. Сейчас они включились одновременно. Через сколько минут это произойдёт снова?

Нужно найти наименьшее число, которое делится и на 6, и на 8. Это НОК:

Следовательно:

Ответ: сигналы снова включатся одновременно через 24 минуты.

В задачах о повторении событий, расписаниях и совпадении периодов обычно применяют НОК.

Задача на выбор между НОД и НОК

Для чисел 18 и 30 нужно определить:

1. наибольший размер одинаковых групп, на которые можно разделить оба количества;
2. через какое минимальное число единиц оба повторяющихся процесса совпадут, если один повторяется через 18 единиц, а другой — через 30.

В первом случае ищут НОД:

Во втором случае ищут НОК:

Ответ:

• для равного разбиения — 6;
• для первого общего момента — 90.

Выбор можно сделать по смыслу условия:

• «разделить на наибольшее число равных групп» — НОД;
• «найти первый общий момент или наименьшее общее количество» — НОК.

Типичные ошибки при нахождении НОД и НОК

Путаница между общим делителем и общим кратным

Общий делитель должен делить каждое из данных чисел. Общее кратное, наоборот, должно само делиться на каждое из них.

Для чисел 4 и 6:

• 2 — общий делитель;
• 12 — общее кратное.

Нельзя назвать 12 НОД: оно не является делителем 4 и 6. Нельзя назвать 2 НОК: оно не делится на 4 и 6.

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

Ошибки при разложении на простые множители

При нахождении НОД из разложений берут только совпадающие простые множители и наименьшие степени. При нахождении НОК берут все встречающиеся простые множители и наибольшие степени.

Например:

Для НОД:

Для НОК:

Частые ошибки:

• пропуск простого множителя;
• неправильная степень множителя;
• использование наибольших степеней при поиске НОД;
• использование только совпадающих множителей при поиске НОК;
• неверное разложение исходного числа.

Полезно проверить разложение обратным умножением. Например:

Неправильное завершение алгоритма Евклида

В алгоритме Евклида ответом является последний ненулевой остаток, а не первый остаток и не последний делитель перед началом вычислений.

Для чисел 70 и 46:

Последний ненулевой остаток — 2, поэтому:

Ошибка возникает, если остановиться на остатке 24 или 22, не продолжив деление. Правильный алгоритм всегда доводят до остатка 0, а ответом считают число, стоящее в предыдущей строке как делитель.