Калькулятор НОД

Q: Чему равен НОД числа и 0?

Любое целое число делит 0, поэтому gcd(a, 0) = |a|. НОД чисел 0 и 0 не определён.

О калькуляторе НОД

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

Калькулятор раскладывает каждое число на простые множители и параллельно выполняет алгоритм Евклида, чтобы вы могли сравнить наглядный способ с самым быстрым.

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

Делитель целого числа делит его без остатка: делители 12 — это 1, 2, 3, 4, 6 и 12. Общий делитель нескольких чисел делит их все, а наибольший общий делитель — самый большой из них. Делители 18 — это 1, 2, 3, 6, 9 и 18, поэтому общие делители 12 и 18 — это 1, 2, 3 и 6, а НОД равен 6.

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

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

Введите от двух до десяти целых чисел через запятую или пробел.
Нажмите «Найти НОД».
Посмотрите разложение каждого числа на простые множители, общие простые множители и деления алгоритма Евклида.

Формулы

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

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

Через разложение на простые множители

\gcd = \prod p^{\min(e_1, e_2, \ldots)}

Каждый общий простой множитель берётся в наименьшей степени.

Связь с НОК

\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |ab|

Разобранный пример: 48, 180

В разобранном примере ищется НОД чисел 48 и 180. Разложение на простые множители даёт $48 = 2^4 \times 3$ и $180 = 2^2 \times 3^2 \times 5$ . Алгоритм Евклида делит 180 на 48 (остаток 36), затем 48 на 36 (остаток 12), затем 36 на 12 (остаток 0), значит, НОД равен 12. Общие простые множители в наименьших степенях, $2^2 \times 3 = 12$ , подтверждают это, а проверка показывает, что 48 и 180, делённые на 12, дают 4 и 15.

Решение ниже построено тем же вычислительным движком, что и калькулятор выше.

Ответ

12

Как мы поняли вашу задачу

Находим наибольший общий делитель (НОД) чисел.

Пошаговое решение

Разложение каждого числа на простые множители
$48 = 2^{4} \times 3,\quad 180 = 2^{2} \times 3^{2} \times 5$
Алгоритм Евклида для GCF(48, 180)
180 = 3 × 48 + 36; 48 = 1 × 36 + 12; 36 = 3 × 12 + 0
$180 = 3 \times 48 + 36 \\ 48 = 1 \times 36 + 12 \\ 36 = 3 \times 12 + 0$
Последний ненулевой остаток и есть НОД
$\gcd(48, 180) = 12$
Проверяем по общим простым множителям
Перемножаем простые множители, общие для всех чисел, каждый в наименьшей степени.
$2^{2} \times 3 = 12$

Использованные формулы

Алгоритм Евклида
$\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a$

12 — наибольшее целое число, на которое делится без остатка каждое из чисел.

Проверка

48 ÷ 12 = 4
180 ÷ 12 = 15

Подробное объяснение

Почему работает алгоритм Евклида

Любое число, которое делит $a$ и $b$ , делит и $a - b$ , а значит, и остаток от деления $a$ на $b$ . Поэтому у пары $(a, b)$ и пары $(b, a \bmod b)$ одни и те же общие делители. Каждый шаг уменьшает числа, и когда остаток становится равным 0, оставшееся число делит само себя и 0, то есть является наибольшим общим делителем. Даже для очень больших чисел алгоритму нужно всего несколько делений, поэтому его используют в компьютерной арифметике и криптографии.

Где нужен НОД

Если разделить числитель и знаменатель на их НОД, дробь сразу становится несократимой: $\frac{48}{180} = \frac{4}{15}$ . В алгебре сначала выносят за скобки НОД коэффициентов, как в $12x + 18 = 6(2x + 3)$ . В житейских задачах он отвечает на вопрос о наибольшем числе одинаковых групп: 24 карандаша, 36 ластиков и 60 наклеек можно разложить не более чем в 12 одинаковых наборов, потому что $\gcd(24, 36, 60) = 12$ .

Разложение на множители или алгоритм Евклида

Разложение на простые множители показывает структуру: видно, какие именно простые множители есть у чисел и почему ответ именно такой. Это помогает при изучении темы или когда нужен ещё и НОК. Слабое место — большие числа раскладывать долго. Алгоритм Евклида ничего не раскладывает: он только делит и запоминает остатки, поэтому остаётся быстрым даже для чисел из десятков цифр. Калькулятор показывает оба способа, чтобы один подтверждал другой.

Типичные ошибки

Перемножать все встречающиеся простые множители, а не только общие.
Брать общий простой множитель в наибольшей степени; для НОД нужна наименьшая.
Считать, что НОД не существует, если числа взаимно простые; в этом случае НОД равен 1.
Останавливать алгоритм Евклида на шаг раньше и записывать последнее неполное частное вместо последнего ненулевого остатка.

Советы

Если одно число делит все остальные, оно и есть НОД.
НОД двух соседних целых чисел всегда равен 1.
Сокращайте дробь на НОД числителя и знаменателя за один шаг.
Проверьте ответ, разделив на него каждое число: у частных не должно быть общих делителей, кроме 1.
Для трёх и более чисел сначала найдите НОД двух, затем объедините результат со следующим числом.

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

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

Это наибольшее натуральное число, на которое все числа набора делятся без остатка. Для 48 и 180 он равен 12.

НОД, GCD, GCF, HCF — это одно и то же?

Да. По-русски говорят НОД, а в англоязычных источниках то же самое число обозначают GCD, GCF или HCF.

Как работает алгоритм Евклида?

Разделите большее число на меньшее и запишите остаток. Замените пару на (меньшее число, остаток) и повторяйте, пока остаток не станет равным 0; последний ненулевой делитель и есть НОД.

Чему равен НОД чисел без общих делителей?

Он равен 1. Такие числа называются взаимно простыми, например 8 и 15.

Можно ли найти НОД отрицательных чисел?

Да. Делимость не зависит от знака: НОД находят по модулям чисел, и он всегда положителен.

Чему равен НОД числа и 0?

Любое целое число делит 0, поэтому $\gcd(a, 0) = |a|$ . НОД чисел 0 и 0 не определён.

Как найти НОД трёх чисел?

Найдите НОД двух чисел, а затем НОД этого результата и третьего числа. Для 24, 36 и 60: $\gcd(24, 36) = 12$ и $\gcd(12, 60) = 12$ .

Как НОД помогает сокращать дроби?

Разделите числитель и знаменатель на их НОД, и дробь сразу станет несократимой. Так как $\gcd(48, 180) = 12$ , получаем $\frac{48}{180} = \frac{4}{15}$ .

Попробуйте калькулятор НОД

Введите свои числа и сравните разложение на простые множители с алгоритмом Евклида.

Открыть калькулятор Спросить ИИ-решатель

О калькуляторе НОД

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

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

Формулы

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

Через разложение на простые множители

Связь с НОК

Разобранный пример: 48, 180

Ответ

Как мы поняли вашу задачу

Пошаговое решение

Использованные формулы

Проверка

Подробное объяснение

Почему работает алгоритм Евклида

Где нужен НОД

Разложение на множители или алгоритм Евклида

Типичные ошибки

Советы

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

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

НОД, GCD, GCF, HCF — это одно и то же?

Как работает алгоритм Евклида?

Чему равен НОД чисел без общих делителей?

Можно ли найти НОД отрицательных чисел?

Чему равен НОД числа и 0?

Как найти НОД трёх чисел?

Как НОД помогает сокращать дроби?

Попробуйте калькулятор НОД

Другие математические калькуляторы