НОД и НОК

Разложение на множители: правило в двух строках

Любое натуральное число больше единицы раскладывается на простые множители единственным способом, и запись удобно сжимать степенями: 72 = 2·2·2·3·3 = 2³·3². Как только разложения готовы, оба ответа собираются механически.

В НОД берут простые, которые встретились у всех чисел сразу, и каждое в наименьшей степени. У 72 = 2³·3² и 108 = 2²·3³ общие простые — двойка и тройка; наименьшие степени 2² и 3², произведение 4·9 = 36. В НОК берут все простые из всех разложений и каждое в наибольшей степени: 2³ и 3³ дают 8·27 = 216. Если общего простого нет ни одного, НОД равен единице: пустое произведение в математике принято считать единицей, и это ровно случай взаимно простых чисел.

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

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

Для 108 и 72 весь путь занимает две строки. Сначала 108 = 72·1 + 36, остаток 36. Затем 72 = 36·2 + 0, остаток обнулился, значит ответ 36. Алгоритму безразличен размер чисел: у пары шестизначных он сходится за десяток шагов, тогда как разложение на множители потребовало бы перебора делителей. Калькулятор считает Евклидом и печатает цепочку остатков целиком.

Связь НОД и НОК

Для двух чисел выполняется равенство НОД(a, b) · НОК(a, b) = a · b. Проверить легко: 36 · 216 = 7776 и 72 · 108 = 7776. Из него же выводится способ считать НОК без разложения — перемножить числа и поделить на НОД. Именно так работает вторая строка панели результата.

Равенство держится только для пары. Для трёх чисел 12, 18 и 24 наибольший общий делитель равен 6, наименьшее общее кратное равно 72, их произведение 432, а произведение самих чисел 5184. Поэтому для списка калькулятор считает НОД и НОК по цепочке: сначала для первых двух чисел, потом результат складывается со следующим, и так до конца списка.

Особые случаи

Ноль делится нацело на любое число, поэтому НОД(a, 0) = a: всё ограничение задаёт второе число. Наименьшее общее кратное с нулём равно нулю по той же причине — ноль кратен всему. Единица делит любое число, значит НОД(a, 1) всегда равен единице, а НОК(a, 1) равен самому числу. Когда одно число делится на другое нацело, ответы вырождаются в сами числа: НОД(4, 12) = 4, НОК(4, 12) = 12. Одинаковые числа дают НОД и НОК, равные им самим.

Взаимно простые числа — отдельный случай, который стоит узнавать в лицо. Общих множителей у них нет, НОД равен 1, а НОК совпадает с произведением: у 7 и 13 это 91, у 8 и 9 это 72. Дробь, собранная из взаимно простых числителя и знаменателя, уже несократима, и вторая вкладка калькулятора сообщает об этом прямо.

Готовые ответы для ходовых пар

Пары, которые чаще всего попадаются в упражнениях. Вторая колонка показывает разложения, из которых собираются оба ответа, — по ней удобно сверять свой черновик.

Что рядом

Сокращение и сложение дробей целиком считает калькулятор дробей, отношения и масштабы — калькулятор пропорций. Разложение на множители опирается на таблицу умножения, её удобно повторить в тренажёре таблицы умножения, а степени и обратный к ним счёт разбирает калькулятор логарифмов. Все вычисления идут в браузере, введённые числа никуда не отправляются.