Калькулятор НОК и НОД

Дроби $\frac{11}{24}$ и $\frac{8}{36}$ нужно сложить, и без общего знаменателя не обойтись. Перемножать 24 на 36 можно, но ответ станет громоздким. Знание НОК сокращает работу: общий знаменатель — 72, а не 864. Калькулятор выше находит и наибольший общий делитель, и наименьшее общее кратное двух чисел, показывая каждый шаг: разложение на множители и деление с остатком. Реши пример сам, потом сверь ход.

Запись НОД и НОК тоже имеет свои правила. Пишут НОД(24; 36) = 12 — в скобках пара чисел через точку с запятой. В англоязычной литературе те же величины называют GCD и LCM, а в формулах используют значки: вертикальные скобки для НОД и квадратные скобки для НОК. На экзамене достаточно русских сокращений, главное — не путать их между собой при письме: перепутанный НОД с НОК в задаче про дроби превращает верное решение в неверное на последней строке.

Делители и кратные: два взгляда на пару чисел

Делитель числа делит его без остатка: у числа 24 делители 1, 2, 3, 4, 6, 8, 12, 24. Кратное, наоборот, само делится на число: 12, 24, 36, 48 — кратные 12. Эти два понятия зеркальны, и для пары чисел интересуют их пересечения.

Общие делители 24 и 36 — это 1, 2, 3, 4, 6, 12; наибольший из них — 12. Это и есть НОД. Общие кратные тех же чисел — 72, 144, 216… и наименьшее — 72: это НОК. НОД ограничен самими числами, а НОК уходит в бесконечность — поэтому говорят «наибольший» и «наименьший».

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

Простые числа делятся только на единицу и себя: 2, 3, 5, 7, 11, 13… Любое составное число собирается из них как конструктор. Разложение ищут последовательным делением: 36 делится на 2 дважды, потом на 3 дважды — выходит $36=2^2\cdot 3^2$. Для 48: $48=2^4\cdot 3$.

Теперь НОД и НОК читаются прямо из разложений. Общие множители идут в НОД в наименьших степенях: у обоих чисел общие $2^2$ и $3$, значит НОД = 4 · 3 = 12. В НОК собирают все множители в наибольших степенях: $2^4\cdot 3^2=144$. Такое правило работает для любой пары, а калькулятор показывает оба разложения рядом.

Формула выше экономит половину работы: нашёл НОД — НОК получаешь одним делением. Для 24 и 36: 864 : 12 = 72. Проверь на числах поменьше: у 4 и 6 НОД равен 2, произведение 24, значит НОК = 12 — сходится.

Алгоритм Евклида: самый старый алгоритм в мире

Разложение удобно для чисел средней величины, но для 1071 и 462 уже tedious. Евклид в «Началах» (около 300 года до н. э.) описал приём проще: дели большее на меньшее с остатком, затем предыдущий делитель на остаток — и так, пока остаток не станет нулём. Последний ненулевой остаток — это НОД.

Ни одного разложения, только деление с остатком — три строки, и готово. Это старейший записанный алгоритм человечества, он до сих пор сидит внутри криптографии и компьютерной арифметики. Калькулятор выше печатает именно эти строки для твоих чисел.

Есть и третий путь — перебор кратных, и его не стоит списывать со счетов. Чтобы найти НОК чисел 6 и 8, выпиши кратные шестёрки: 6, 12, 18, 24 — стоп, 24 делится и на 8. Ответ готов без всяких разложений. Для небольших чисел этот способ быстрее, чем кажется, и он отлично работает как самопроверка: если разложение дало другой ответ — где-то арифметическая описка.

С делителями симметричный приём — перебор от меньшего числа вниз. Ищем НОД чисел 30 и 42: делим 30 на 3, 2, и постепенно добираемся до 6 — а 42 на 6 делится, значит ответ 6. Полный перебор делителей обоих чисел занял бы больше времени, поэтому здесь Евклид всё-таки король: для больших чисел он в разы короче любого перебора.

Отдельно про простые числа: они всегда взаимно просты между собой, ведь их единственные делители — единица и они сами. Пара 13 и 17 даёт НОД 1 и НОК 221. Это свойство лежит в основе шифрования с открытым ключом: там специально выбирают большие простые числа, и вся современная банковская криптография опирается на то, что искать их НОД легко, а разлагать произведение обратно на множители — практически невозможно. Школьный алгоритм Евклида и защита карт при переводе — дальние родственники.

Разложение больших чисел имеет свою технику. Дели последовательно на 2, пока делится, потом на 3, на 5, на 7 — и так по списку простых. Для 360: четыре двойки (360 → 180 → 90 → 45), затем две тройки (45 → 15 → 5), в остатке пятёрка. Запись выглядит как лесенка и читается снизу вверх: 360 = 2 · 2 · 2 · 2 · 3 · 3 · 5. Проверка простая: перемножь обратно — должно получиться исходное число.

Из разложений видно и внутреннее устройство чисел. Число с нечётным количеством множителей — точный квадрат: у 36 разложение даёт чётные степени, и корень извлекается нацело. Числа с разными наборами множителей не имеют общих больших кусков — вот почему взаимная простота так важна для дробей. Так арифметика шестого класса незаметно готовит к теории чисел и даже к криптографии: идея одна — любое число собирается из простых кирпичиков, и весь вопрос в том, какие кирпичики общие.

Где НОК и НОД встречаются в задачах

Классика про периодичность: два автобуса выходят с конечной каждые 12 и 18 минут. Совпали в 9:00 — когда снова выйдут вместе? Время совпадения должно делиться и на 12, и на 18, то есть быть общим кратным; ближайшее — НОК = 36. Ответ: в 9:36. Такие задачи на ОГЭ встречаются регулярно, и НОК решает их одной строкой.

НОД работает в противоположных ситуациях. Разрезаем лист 24 на 36 сантиметров на одинаковые квадраты без обрезков — сторона квадрата обязана быть общим делителем, и самый крупный квадрат имеет сторону 12. Тот же вопрос про плитку, упаковку и разбиение отрезков. И, конечно, дроби: НОД сокращает, НОК приводит к общему знаменателю — это две стороны одной пары чисел.