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

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

Популярный AI Skill PRO

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

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

GCF=gcd⁡(Числа)\text{GCF} = \gcd\left(\text{Числа}\right)
Статистика использования

Реклама

Результаты

Наибольший общий делитель
42
Разложение на простые множители
84 22 × 3 × 7
126 2 × 32 × 7
Общие простые множители 2 × 3 × 7 = 42

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

Что считает калькулятор НОД

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

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

Поле для ввода всего одно — оно называется числа. Введите два или более целых числа через запятую, например 24, 36, 60. После этого калькулятор:

  • Разбивает текст по запятым и убирает лишние пробелы.
  • Оставляет только корректные целые числа — по шаблону -?\d+, поэтому отрицательные числа допускаются, а дроби, десятичные значения и посторонний текст игнорируются.
  • Вычисляет НОД по всем корректным числам и показывает результат.

Поскольку нецелые значения просто отбрасываются, аккуратный список чисел через запятую даёт самый надёжный ответ.

Какая формула используется

Калькулятор не перебирает все возможные делители подряд. Вместо этого он применяет алгоритм Евклида к парам чисел и «сворачивает» список по шагам. Если говорить проще, он вычисляет:

$$\text{GCF} = \gcd\left(\text{Numbers}\right)$$
  • НОД(a, b) по классическому алгоритму нахождения наибольшего общего делителя.
  • Затем НОД(полученный результат, c), потом НОД(этот результат, d) и так далее по всему списку.

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

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

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

Допустим, вы вводите 24, 36, 60:

  • \(\gcd(24, 36) = 12\)
  • \(\gcd(12, 60) = 12\)

Значит, калькулятор вернёт 12. Проверить легко: \(24 \div 12 = 2\), \(36 \div 12 = 3\) и \(60 \div 12 = 5\) — все результаты целые, и никакое большее число не делит все три без остатка.

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

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

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

А как насчёт отрицательных чисел? Отрицательные числа допустимы. НОД всегда выводится как положительное значение, поскольку делимость не зависит от знака (например, \(\gcd(-8, 12) = 4\)).

Почему моё десятичное число проигнорировано? Калькулятор учитывает только целые числа. Любое значение с десятичной точкой, а также нечисловой текст отбрасываются до расчёта, поэтому вводите целые числа через запятую.

Как найти НОД вручную

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

Метод 1 — разложение на простые множители

  1. Представьте каждое число как произведение простых чисел. Пример: \(24 = 2^3 \cdot 3\) и \(36 = 2^2 \cdot 3^2\).
  2. Оставьте только простые числа, которые появляются в каждом разложении. Здесь оба содержат 2 и 3.
  3. Присвойте каждому общему простому числу его наименьший показатель среди чисел: \(2^{\min(3,2)} = 2^2\) и \(3^{\min(1,2)} = 3^1\).
  4. Умножьте эти степени: $$\gcd(24,36) = 2^2 \cdot 3 = 4 \cdot 3 = \text{12}$$ поэтому НОД равен 12.
  5. Если никакое простое число не является общим для всех чисел, НОД равен 1.

Метод 2 — алгоритм Евклида (лучше всего для больших чисел)

Алгоритм Евклида полностью избегает разложения на множители. Он основан на том, что \(\gcd(a,b) = \gcd(b,\; a \bmod b)\).

  1. Разделите большее число на меньшее и сохраните остаток.
  2. Замените большее число на меньшее, а меньшее на остаток.
  3. Повторяйте до тех пор, пока остаток не будет равен 0. Последний ненулевой остаток — это НОД.

Для \(\gcd(1071, 462)\):

  1. \(1071 = 2 \times 462 + 147\)
  2. \(462 = 3 \times 147 + 21\)
  3. \(147 = 7 \times 21 + 0\)
  4. Остаток 0 достигнут, поэтому последний ненулевой остаток, 21, — это НОД.

Метод 3 — перечисление делителей (только для малых чисел)

Выпишите все делители каждого числа, обведите те, которые они имеют в общем, и выберите наибольший. Делители 18: 1, 2, 3, 6, 9, 18. Делители 30: 1, 2, 3, 5, 6, 10, 15, 30. Общие делители: 1, 2, 3, 6 → НОД = 6. Это надежно, но медленно, когда числа превышают две цифры.

Три или более чисел — правило складывания

НОД ассоциативен, поэтому вы можете сократить длинный список по два числа за раз:

$$\gcd(a,b,c) = \gcd\bigl(\gcd(a,b),\, c\bigr)$$

Например, \(\gcd(30, 42, 70)\): сначала \(\gcd(30,42) = 6\), затем \(\gcd(6,70) = 2\). Порядок складывания не изменяет результат. Поскольку каждое складывание может только уменьшить текущее значение, вы можете остановиться, как только текущий НОД достигнет 1.

Знак не имеет значения: делимость не зависит от знака, поэтому \(\gcd(-a,b) = \gcd(a,b)\) и НОД всегда сообщается как положительное число.

Реклама

Ключевые термины и определения

Термин Определение
Делитель Целое число, которое делит другое целое число точно, оставляя остаток 0. Например, 7 является делителем 42, потому что \(42 = 7 \times 6\).
Общий делитель Число, которое является делителем каждого числа в наборе. 1 является общим делителем любого набора целых чисел.
Наибольший общий делитель (НОД) Наибольшее положительное целое число, которое делит все числа в наборе. Также называется наибольшим общим делителем (GCD) или в британских и индийских учебниках наибольшим общим множителем (HCF) — все три названия означают одно и то же.
Простое число Целое число больше 1, единственными положительными делителями которого являются 1 и само число: 2, 3, 5, 7, 11, 13, … Обратите внимание, что 1 не является простым числом.
Составное число Целое число больше 1, которое не является простым, то есть оно имеет по крайней мере один делитель, отличный от 1 и самого себя.
Разложение на простые множители Представление числа как произведения простых чисел, например \(360 = 2^3 \cdot 3^2 \cdot 5\). По фундаментальной теореме арифметики это разложение уникально, кроме порядка множителей.
Взаимно простые (относительно простые) Два или более чисел, НОД которых равен 1, например 14 и 25. Они не имеют общего простого множителя, хотя ни одно из них не обязательно должно быть простым.
Наименьшее общее кратное (НОК) Наименьшее положительное целое число, на которое делится каждое число в наборе, например \(\operatorname{lcm}(4,6) = 12\).
Несократимая форма Дробь находится в несократимой форме, когда НОД ее числителя и знаменателя равен 1.

Два тождества, достойные запоминания

Для любых двух ненулевых целых чисел \(a\) и \(b\) произведение НОД и НОК равно абсолютному значению произведения:

$$\gcd(a,b) \times \operatorname{lcm}(a,b) = |a \times b|$$

Поэтому, как только вы знаете НОД, вы получаете НОК бесплатно: при \(a = 24\), \(b = 36\) и \(\gcd = 12\) получаем \(\operatorname{lcm} = (24 \times 36) / 12 = 864 / 12 = 72\). Осторожно: это тождество справедливо только для двух чисел — оно не распространяется без изменений на три или более.

Второе тождество рассматривает ноль: каждое целое число делит 0, поэтому

$$\gcd(a, 0) = |a|, \qquad \gcd(0,0) = 0$$

Вот почему добавление 0 в ваш список никогда не меняет ответ, и почему \(\gcd(0,0)\) по соглашению определяется как 0.

Соглашения и граничные случаи

Каждый случай ниже был прогнан через этот калькулятор; в столбце результата — то, что он действительно возвращает.

СлучайВводРезультат
С отрицательным числом (−12 и 18)-12, 18GCF = 6
С нулём (0 и 12)0, 12GCF = 12

Проверено 2026-11-08

Дополнительные решенные примеры

Пример 1 — пара взаимно простых чисел: gcd(14, 25)

Разложение на простые множители: \(14 = 2 \cdot 7\) и \(25 = 5^2\). Два списка не имеют общего простого числа, поэтому единственный общий делитель — это 1.

Проверка с помощью алгоритма Евклида:

  1. \(25 = 1 \times 14 + 11\)
  2. \(14 = 1 \times 11 + 3\)
  3. \(11 = 3 \times 3 + 2\)
  4. \(3 = 1 \times 2 + 1\)
  5. \(2 = 2 \times 1 + 0\)

Последний ненулевой остаток равен 1, поэтому \(\gcd(14,25) = 1\) и числа взаимно простые. Дробь такая как \(\tfrac{14}{25}\) поэтому уже находится в несократимой форме.

Пример 2 — упрощение дроби 84/126

  1. Разложите обе части на множители: \(84 = 2^2 \cdot 3 \cdot 7\), \(126 = 2 \cdot 3^2 \cdot 7\).
  2. Общие простые числа с их наименьшими показателями: \(2^1 \cdot 3^1 \cdot 7^1\).
  3. Умножьте: \(2 \cdot 3 \cdot 7 = 42\), поэтому НОД равен 42.
  4. Разделите числитель и знаменатель на 42: $$\frac{84}{126} = \frac{84 \div 42}{126 \div 42} = \frac{2}{3}$$

Поскольку \(\gcd(2,3) = 1\), результат полностью сокращен. Деление на что-либо меньшее, чем НОД — скажем 6, дающее \(\tfrac{14}{21}\) — оставляет работу еще предстоящей.

Пример 3 — смешанный набор с отрицательным числом: gcd(−18, 45, 9)

Знаки опускаются в первую очередь, поскольку делимость не зависит от знака: задача становится \(\gcd(18, 45, 9)\). Теперь складывайте слева направо.

  1. \(\gcd(18,45)\): \(45 = 2 \times 18 + 9\), затем \(18 = 2 \times 9 + 0\) → НОД равен 9.
  2. Включите третье число: \(\gcd(9, 9) = 9\).

Поэтому \(\gcd(-18, 45, 9) = \) 9. Ответ положительный, несмотря на то что одно входное значение было отрицательным, и здесь НОД равен одному из входных значений — это всегда происходит, когда одно число делит все остальные.

Пример 4 — четыре числа: gcd(48, 72, 120, 180)

По разложению на простые множители. Разложите каждое:

Число Разложение на простые множители Степень 2 Степень 3 Степень 5
48 \(2^4 \cdot 3\) \(2^4\) \(3^1\) —
72 \(2^3 \cdot 3^2\) \(2^3\) \(3^2\) —
120 \(2^3 \cdot 3 \cdot 5\) \(2^3\) \(3^1\) \(5^1\)
180 \(2^2 \cdot 3^2 \cdot 5\) \(2^2\) \(3^2\) \(5^1\)

Простое число 5 отсутствует в 48 и 72, поэтому оно исключается. Общие простые числа с их наименьшими показателями дают

$$\gcd(48,72,120,180) = 2^2 \cdot 3 = 4 \cdot 3 = 12$$

По методу складывания Евклида. Используя \(\gcd(a,b,c,d) = \gcd(\gcd(\gcd(a,b),c),d)\):

  1. \(\gcd(48,72)\): \(72 = 1 \times 48 + 24\); \(48 = 2 \times 24 + 0\) → 24.
  2. \(\gcd(24,120)\): \(120 = 5 \times 24 + 0\) → 24.
  3. \(\gcd(24,180)\): \(180 = 7 \times 24 + 12\); \(24 = 2 \times 12 + 0\) → 12.

Оба маршрута согласны: НОД равен 12. Проверьте ответ, разделив: 48/12 = 4, 72/12 = 6, 120/12 = 10, 180/12 = 15 — все целые числа, и \(\gcd(4,6,10,15) = 1\), подтверждая, что ничего большего не было пропущено.

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

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

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