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

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

Развивающийся AI Skill PRO

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

введите целые числа через запятую

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

gcd⁡(Числа n1,n2,…,nk)=gгде{g=gcd⁡(gcd⁡(n1,n2),…,nk)gcd⁡(a,b)=gcd⁡(b,amodb),gcd⁡(a,0)=aОбщие делители={d∈ℤ+:gmodd=0}\begin{gathered} \gcd\left({{\text{Числа } n_1, n_2, \dots, n_k}}\right) = g \\[1.5em] \text{где}\quad \left\{ \begin{aligned} g &= \gcd\left(\gcd(n_1, n_2), \dots, n_k\right) \\ \gcd(a,b) &= \gcd(b,\; a \bmod b), \quad \gcd(a,0) = a \\ \text{Общие делители} &= \{\, d \in \mathbb{Z}^{+} : g \bmod d = 0 \,\} \end{aligned} \right. \end{gathered}
Показать шаги расчёта (1)
  1. Делители каждого числа

    F(n)={d∈ℤ+:nmodd=0}=⋃i=1⌊n⌋{i,ni}nmodi=0,n∈ЧислаF(n) = \{\, d \in \mathbb{Z}^{+} : n \bmod d = 0 \,\} = \bigcup_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor} \left\{ i,\; \tfrac{n}{i} \right\}_{\, n \bmod i = 0}, \quad n \in \text{Числа}

    Для каждого введённого числа программа перечисляет все положительные делители, перебирая i до квадратного корня и сопоставляя i с n, делённым на i.

Статистика использования

Реклама

Результаты

Наибольший общий делитель
8
НОД (наибольший общий делитель)
Делители числа 16 1, 2, 4, 8, 16
Делители числа 24 1, 2, 3, 4, 6, 8, 12, 24
Делители числа 64 1, 2, 4, 8, 16, 32, 64
Делители числа 136 1, 2, 4, 8, 17, 34, 68, 136
Общие делители: 1, 2, 4, 8

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

Что делает этот калькулятор

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

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

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

Введите целые числа через запятую, например 136, 64, 24, 16, и сразу получите результат. Для каждого числа делители выводятся по возрастанию, затем показываются общие делители и единственное значение НОД. Используйте только целые положительные числа: ноль, отрицательные значения и дроби в качестве делителей не подходят.

Как это считается

Целое число d является делителем числа n, если \(n \bmod d = 0\) (то есть деление выполняется без остатка). Чтобы быстро найти все делители, мы перебираем i от 1 до квадратного корня из n: как только i делит n, делителями сразу являются и i, и \(n/i\). НОД для списка вычисляется попарно по алгоритму Евклида: пока b не равно нулю, заменяем пару (a, b) на (b, a mod b); оставшееся значение a и есть НОД. Формально:

$$\gcd(a, 0) = a, \quad \gcd(a, b) = \gcd(b, \; a \bmod b)$$

Полезный факт: общие делители всего набора — это в точности делители самого НОД:

$$\text{CommonFactors} = \{\, d : g \bmod d = 0 \,\}, \quad g = \gcd(n_1, n_2, \dots)$$

Реклама
Блок-схема алгоритма Евклида, многократно заменяющего числа остатком
Алгоритм Евклида многократно заменяет (a, b) на (b, a mod b), пока b не станет 0.

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

Возьмём числа 136, 64, 24, 16. Делители 16: 1, 2, 4, 8, 16; делители 24: 1, 2, 3, 4, 6, 8, 12, 24; делители 64: 1, 2, 4, 8, 16, 32, 64; делители 136: 1, 2, 4, 8, 17, 34, 68, 136. По алгоритму Евклида: \(\gcd(16, 24) = 8\), затем \(\gcd(8, 64) = 8\), затем \(\gcd(8, 136) = 8\) — значит, НОД = 8. Делители числа 8: 1, 2, 4, 8 — это и есть общие делители всего набора.

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

НОД и GCD — это одно и то же? Да. Наибольший общий делитель (НОД), greatest common factor (GCF) и greatest common divisor (GCD) — это разные названия одной и той же величины.

А если у чисел нет общих делителей? У любого набора целых положительных чисел есть общий делитель 1, поэтому множество общих делителей всегда содержит как минимум \(\{1\}\), а НОД не меньше 1. Числа, у которых единственный общий делитель — это 1, называют взаимно простыми.

Можно ввести только одно число? Да — тогда выводятся его делители, а НОД равен самому этому числу.

Результаты НОД для разных типов наборов чисел

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

Числа НОД Общие делители Тип связи
8 и 15 1 1 Взаимно простые (нет общего делителя, кроме 1)
12 и 36 12 1, 2, 3, 4, 6, 12 Кратность (36 кратно 12)
18, 24, 30 6 1, 2, 3, 6 Три числа с общим делителем
17 и 31 1 1 Два разных простых числа (всегда взаимно простые)
20 и 20 20 1, 2, 4, 5, 10, 20 Одинаковые числа (НОД равен самому числу)
48 и 180 12 1, 2, 3, 4, 6, 12 Частичное совпадение простых множителей

Проверка для 48 и 180: \(48 = 2^4 \cdot 3\) и \(180 = 2^2 \cdot 3^2 \cdot 5\). Берём наименьшую степень каждого общего простого числа: \(2^2 \cdot 3 = 12\).

Реклама

Что говорит НОД и где он применяется

  • НОД = 1 означает взаимную простоту. Числа не имеют общего простого делителя. Сами они не обязаны быть простыми: 8 и 15 взаимно просты, хотя ни одно из них не является простым.
  • НОД равен наименьшему числу. Это наименьшее число делит все остальные. Например, \(\gcd(12, 36) = 12\).
  • Сокращение дробей. Деление числителя и знаменателя на их НОД приводит дробь к несократимому виду за один шаг. Так как \(\gcd(24, 36) = 12\), получаем \(\frac{24}{36} = \frac{24 \div 12}{36 \div 12} = \frac{2}{3}\).
  • Наибольшие равные группы. Если у вас 24 ручки и 36 карандашей и вы хотите составить одинаковые группы, используя все предметы, наибольшее число групп — \(\gcd(24, 36) = 12\). В каждой группе 2 ручки и 3 карандаша.
  • Квадратные плитки. Наибольшая квадратная плитка, которая точно укладывается на участок 48 см на 180 см без резки, имеет сторону \(\gcd(48, 180) = 12\) см. Это 4 плитки в одну сторону и 15 в другую.
  • Связь с НОК. Для двух натуральных чисел \(\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b\). Пример: \(\gcd(12, 18) = 6\) и \(\operatorname{lcm}(12, 18) = 36\), поэтому \(6 \cdot 36 = 216 = 12 \cdot 18\). Это тождество справедливо только для двух чисел, но не для трёх и более.

Ключевые термины: делитель, общий делитель, НОД, взаимно простые

Делитель (фактор)
Натуральное число, которое делит данное число без остатка. Делители 12: 1, 2, 3, 4, 6 и 12.
Кратное
Произведение числа и любого целого числа. Кратные 4 включают 4, 8, 12 и 16. Если \(d\) — делитель \(n\), то \(n\) кратно \(d\).
Общий делитель
Число, которое является делителем каждого числа в наборе. Для 12 и 18 общие делители: 1, 2, 3 и 6.
НОД (GCF / GCD / HCF)
Наибольший общий делитель, он же наибольший общий фактор. Это наибольший из общих делителей. Все три обозначения означают одно и то же.
Взаимно простые (относительно простые)
Числа, единственный общий делитель которых — 1, поэтому их НОД равен 1.
Простое число
Целое число больше 1, единственные натуральные делители которого — 1 и оно само, например 2, 3, 5, 7, 11, 17 и 31.
Алгоритм Евклида
Метод, который многократно заменяет пару \((a, b)\) на \((b,\; a \bmod b)\), пока остаток не станет равен 0. Последнее ненулевое значение и есть НОД. Пример: \(\gcd(180, 48)\): \(180 = 3 \cdot 48 + 36\), затем \(48 = 1 \cdot 36 + 12\), затем \(36 = 3 \cdot 12 + 0\), значит НОД равен 12. Для более чем двух чисел применяйте его поэтапно: \(\gcd(\gcd(n_1, n_2), n_3)\).
Последнее обновление:

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

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