НОД и НОК двух чисел

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

Чтобы найти НОД, делят большее число на меньшее и берут остаток. Затем делят меньшее число на этот остаток и снова берут остаток. Процесс продолжается, пока остаток не станет нулём, а последний ненулевой остаток и есть НОД. Метод основан на том, что НОД(a, b) = НОД(b, a mod b).

Для чисел 84 и 126 получаем цепочку: 126 = 1 · 84 + 42, затем 84 = 2 · 42 + 0. Остаток нуль достигнут на втором шаге, значит НОД равен 42. Алгоритм работает быстро даже для огромных чисел, потому что остатки убывают очень быстро.

Как найти НОК и проверить результат

НОК проще всего найти через НОД по формуле НОК(a, b) = |a · b| / НОД(a, b). Для 84 и 126 это 84 · 126 / 42 = 252. Проверка простая: 252 делится на 84 (получается 3) и на 126 (получается 2), и меньшего общего кратного нет.

Из той же формулы следует, что НОД(a, b) · НОК(a, b) = |a · b|. Это удобная самопроверка: перемножьте полученные НОД и НОК и сравните с произведением исходных чисел. Для чисел 84 и 126 оба произведения равны 10 584.

Применение к дробям

НОД используют для сокращения дробей: чтобы сократить 84/126, делят числитель и знаменатель на 42 и получают 2/3. Полученная дробь несократима, потому что НОД числителя и знаменателя равен единице.

НОК нужен при сложении дробей с разными знаменателями. Чтобы сложить 1/84 и 1/126, берут общий знаменатель 252: получается 3/252 + 2/252 = 5/252. Наименьший общий знаменатель делает числа в расчётах как можно меньше.

Задачи на совпадение периодов

НОК применяют, когда два события повторяются с разными периодами. Если один автобус отправляется каждые 12 минут, а другой каждые 18, то совместно они отправятся через НОК(12, 18) = 36 минут. Так же рассчитывают совпадения циклов обслуживания и расписаний.

НОД помогает при делении на равные части: если надо разрезать полотно 84 на 126 см на одинаковые квадраты наибольшего размера, сторона квадрата равна НОД, то есть 42 см. Оба числа в этих задачах легко получить одним расчётом.

Особые случаи и ограничения

Знаки чисел не влияют на результат, поскольку используются модули: для −48 и 180 НОД равен 12. Если одно из чисел равно нулю, НОД равен модулю другого числа, а НОК обращается в ноль, так как нулевое кратное делится на любое число.

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

Формула расчёта

Проверенные примеры

Как пользоваться онлайн-калькулятором

1. Введите первое целое число.
2. Введите второе целое число.
3. Нажмите «Рассчитать»: получите НОД и НОК.