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

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

Наибольший общий делитель (НОД) — это наибольшее положительное целое число, которое делит каждое число заданного набора без остатка. Например, НОД чисел 12 и 18 равен 6, потому что 6 — это наибольшее число, которое делит и 12, и 18 нацело.

Этот калькулятор находит НОД двух или более положительных целых чисел. В качестве дополнения он также показывает наименьшее общее кратное (НОК): наименьшее положительное целое число, кратное каждому числу из набора.

Как работает калькулятор?

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

Алгоритм Евклида находит НОД двух чисел, многократно заменяя большее число остатком от деления большего на меньшее, пока остаток не станет равным нулю. Последнее ненулевое значение и есть НОД. Чтобы обработать весь список, НОД вычисляется попарно: нод(a, b, c) = нод(нод(a, b), c), и так далее.

Формулы

НОД списка чисел вычисляется путём попарного свёртывания НОД:

$\text{GCF}(a_1, a_2, \ldots, a_n) = \gcd(\ldots\gcd(\gcd(a_1, a_2), a_3)\ldots, a_n)$

НОК двух чисел следует непосредственно из их НОД:

$\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$

Решённые примеры

1. Два числа: $\gcd(12, 18) = 6$ и $\text{lcm}(12, 18) = 36$. Делители числа 12 — это 1, 2, 3, 4, 6, 12, а числа 18 — 1, 2, 3, 6, 9, 18; наибольший общий делитель — 6.

2. Три числа: $\gcd(8, 12, 16) = 4$. Каждое из чисел 8, 12 и 16 делится на 4, и ничто большее не делит все три.

3. Взаимно простые числа: $\gcd(7, 13) = 1$. И 7, и 13 — простые числа, поэтому у них нет общего делителя, кроме 1 — они взаимно простые.

4. Больший набор: $\gcd(100, 75, 50) = 25$. Число 25 делит все три, тогда как 50 не делит 75.

Практические замечания

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