Найти НОД и НОК чисел онлайн

Как найти НОД и НОК

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

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

Для двух чисел верно: $\text{НОД}(a, b) \cdot \text{НОК}(a, b) = a \cdot b$.

Пример. НОД и НОК чисел 24 и 36

$$24 = 2^3 \cdot 3, \qquad 36 = 2^2 \cdot 3^2$$$$\text{НОД}(24, 36) = 2^2 \cdot 3 = 12, \qquad \text{НОК}(24, 36) = 2^3 \cdot 3^2 = 72$$

Проверка: $12 \cdot 72 = 864 = 24 \cdot 36$.

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

Большее число делим на меньшее с остатком, потом делитель — на остаток, и так до нулевого остатка. Последний ненулевой остаток и есть НОД:

$$126 = 84 \cdot 1 + 42, \qquad 84 = 42 \cdot 2 + 0 \;\Rightarrow\; \text{НОД}(126, 84) = 42$$

Частые вопросы

Зачем нужен НОК? Чтобы найти общий знаменатель дробей — см. калькулятор дробей.

Что значит «взаимно простые числа»? Это числа, у которых НОД = 1, например 13 и 17. Их НОК равен произведению.