Калькулятор наибольшего общего делителя (НОД)

Калькулятор наибольшего общего делителя (НОД)

Растущий AI Skill PRO

Введите расчет

Математическая формула

GCF(a,b)=gcd⁡(a,b)LCM(a,b)=a·bgcd⁡(a,b)где{a=|Первое число|b=|Второе число|\begin{gathered} \text{GCF}(a, b) = \gcd(a, b) \qquad \text{LCM}(a, b) = \frac{a \cdot b}{\gcd(a, b)} \\[1.5em] \text{где}\quad \left\{ \begin{aligned} a &= |\text{Первое число}| \\ b &= |\text{Второе число}| \end{aligned} \right. \end{gathered}
Статистика использования

Реклама

Результаты

Наибольший общий делитель
12
НОД(48, 36)
Наибольший общий делитель (НОД) 12
Наименьшее общее кратное (НОК) 144
Алгоритм Евклида
48 = 1 × 36 + 12
36 = 3 × 12 + 0

НОД — последний делитель, при котором остаток равен 0.

Сообщить об ошибке на этой странице

Что такое наибольший общий делитель?

Наибольший общий делитель (НОД) — это самое большое целое положительное число, на которое без остатка делятся оба заданных целых числа. В англоязычной литературе его обозначают как GCF (greatest common factor), GCD (greatest common divisor) или HCF (highest common factor) — это просто разные названия одной и той же величины. Например, НОД чисел 48 и 36 равен 12, потому что 12 — наибольшее число, на которое нацело делятся оба. Этот калькулятор мгновенно находит НОД, а заодно вычисляет и наименьшее общее кратное (НОК).

Два пересекающихся круга простых множителей; общие множители в пересечении образуют НОД
НОД — это произведение простых множителей, общих для обоих чисел.

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

Введите два неотрицательных целых числа в поля a и b и нажмите кнопку расчёта. Калькулятор выдаст наибольший общий делитель и наименьшее общее кратное. Порядок чисел не важен — \(\text{НОД}(48, 36)\) равен \(\text{НОД}(36, 48)\).

Как это работает: формула

В основе расчёта лежит алгоритм Евклида — изящный метод, известный ещё со времён Древней Греции. Он опирается на простой факт: НОД двух чисел делит и их остаток от деления. Пару \((a, b)\) последовательно заменяют на \((b, a \bmod b)\) до тех пор, пока второе число не станет равным нулю; оставшееся первое число и есть искомый НОД. Наименьшее общее кратное затем находится по формуле

$$\text{НОК}(a, b) = \frac{a \times b}{\text{НОД}(a, b)}$$
Реклама
Блок-схема алгоритма Евклида: деление и замена, пока остаток не станет нулём
Алгоритм Евклида многократно заменяет \((a, b)\) на \((b, a \bmod b)\), пока \(b\) не станет 0.

Разбор примера

Найдём НОД чисел 48 и 36. Шаг 1: \(48 \bmod 36 = 12\), значит пара превращается в \((36, 12)\). Шаг 2: \(36 \bmod 12 = 0\), и пара становится \((12, 0)\). Поскольку второе число равно 0, НОД равен 12. Наименьшее общее кратное:

$$\text{НОК} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$

Часто задаваемые вопросы

Чему равен НОД, если одно из чисел равно 0? По определению \(\text{НОД}(a, 0) = a\). А \(\text{НОД}(0, 0)\) равен 0.

Это то же самое, что HCF или GCD? Да. GCF, GCD и HCF — это разные обозначения одной и той же величины, которую в русском языке называют НОД.

Что будет, если у чисел нет общих делителей? Тогда НОД равен 1, а сами числа называют взаимно простыми.

Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика