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

24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5 ⇒ НОД(24, 36, 60) = 2² × 3 = 12, а все общие делители — 1, 2, 3, 4, 6, 12

24, 36, 60

Числа для сравнения — от двух до десяти, каждое целое от 1 до 1 000 000. Разделяйте их пробелами, запятыми или точками с запятой, поэтому 24 36 60 и 24, 36, 60 — один и тот же ввод. Десятичная запись и дробная черта отклоняются, а не округляются, как и 0: единого соглашения о НОД(0, 0) нет, и страница не станет выбирать его за вас

2³ × 3

Разложение числа 24 на простые множители: три двойки и одна тройка. У каждого целого числа больше 1 такое разложение ровно одно — именно поэтому работает второй способ

2² × 3

Общая часть всех трёх разложений: две двойки и одна тройка, то есть 4 × 3 = 12. Берут наименьшую степень каждого общего простого множителя, а не наибольшую: делитель должен делить все числа списка, поэтому он не может быть больше того, что допускает самое скупое из них

1, 2, 3, 4, 6, 12

Все общие делители по возрастанию. Последний из них и есть наибольший общий делитель, а сам список служит проверкой: 12 делит 24, 36 и 60 без остатка, а следующий делитель выше него, 18, делит только 36

НОД(a, b, c) = НОД(НОД(a, b), c)

Как поступать с более чем двумя числами: по два за раз, вкладывая текущий результат в следующее число. Это не отдельный метод, а тот же способ для двух чисел, применённый несколько раз, — поэтому страница даёт одинаковый ответ и для трёх чисел, и для любой пары, с которой вы начнёте

взаимно простые

Название для пары, единственный общий делитель которой равен 1, то есть НОД равен 1. Числа 9 и 20 взаимно простые, хотя ни одно из них не простое, а любые два последовательных целых числа взаимно просты всегда

Сокращение дроби — повседневный случай: 24/36 превращается в 2/3, если разделить обе части на 12, и этот шаг открывает любую работу с дробями. Приведение отношения к наименьшим целым числам — та же операция в другой одежде: смесь, записанная как 24 : 36 : 60, — это та же смесь, что 2 : 3 : 5, и на этикетку помещается именно вторая запись. В учебных задачах делитель спрашивают напрямую, и напечатанный список общих делителей служит решением: видно, что ответ найден сравнением делителей, а не угадан. Есть ещё два места, где он всплывает. Выкладывание прямоугольника плитками наибольшего возможного размера — это вопрос о наибольшем общем делителе в маскировке, а ответ и есть размер плитки. А в теории чисел взаимная простота двух чисел — то условие, от которого зависят несколько результатов, включая тот, на котором держится шифрование RSA: модуль надёжен только тогда, когда он взаимно прост с используемым показателем. Когда числа неудобные, как 1071 и 462, разложение вручную перестаёт быть практичным и очередь доходит до алгоритма Евклида: в примерах страницы оба пути дают одно и то же число 21.

1. Наибольший общий делитель чисел 24, 36 и 60

   1. Делители 24: 1, 2, 3, 4, 6, 8, 12, 24
   2. Делители 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
   3. Делители 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
   4. Оставляем те, что есть во всех трёх списках: 1, 2, 3, 4, 6, 12
   5. Наибольший из них — 12, значит наибольший общий делитель равен 12

   Ввод по умолчанию, и ровно его таблица ниже разбирает целиком. Через разложение на простые множители выходит то же самое: 24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5, у всех трёх общими оказываются 2² и одна 3, а 2² × 3 = 12. Ценнее всего здесь список общих делителей: только он показывает, что 12 — наибольший, а не просто один из общих, ведь 8 и 9 делят по два числа из трёх, но не все три.

2. Неудобные числа: 1071 и 462

   1. 1071 ÷ 462 = 2, остаток 147
   2. 462 ÷ 147 = 3, остаток 21
   3. 147 ÷ 21 = 7, остаток 0 — остаток дошёл до нуля, останавливаемся
   4. Последний ненулевой остаток равен 21, значит наибольший общий делитель равен 21
   5. Проверка разложением: 1071 = 3 × 7 × 51 и 462 = 2 × 3 × 7 × 11, общая часть — 3 × 7

   Эта пара и объясняет, зачем на странице алгоритм Евклида: ни одно из чисел не раскладывается на глаз, а выписывать делители вручную долго и легко ошибиться. Четырёх делений хватает. Ответ 21 — ещё и наибольшее число, которое делит оба, а общий список короткий: 1, 3, 7, 21. Обычно это признак того, что общего у чисел мало.

3. Взаимно простые числа: 9 и 20

   1. Делители 9: 1, 3, 9
   2. Делители 20: 1, 2, 4, 5, 10, 20
   3. Единственный делитель, который есть в обоих списках, — 1
   4. Значит, наибольший общий делитель равен 1

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

4. Число в паре с самим собой: 36 и 36

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

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

Каждое число должно быть целым, от 1 до 1 000 000, и всего чисел должно быть от двух до десяти. Ноль отклоняется, и это решение, а не упущение: НОД(0, 5) в одной распространённой традиции равен 5, а в других не определён, НОД(0, 0) в части учебников равен 0, а в остальных не определён вовсе. Напечатать один из этих ответов значило бы соврать читателю, который придерживается другого соглашения, поэтому страница просит положительные числа. Отрицательные отклоняются по той же причине: НОД(−24, 36) в большинстве изложений равен 12, но правила знаков — отдельное соглашение, которого эта страница не заявляет. Дробные записи отклоняются, а не округляются: наибольший общий делитель говорит о делении целых на целые, а 2,5 ÷ 1,25 делится без остатка, и ответ потерял бы смысл. Разделителями могут быть пробелы, запятые или точки с запятой, в любом сочетании; всё остальное считается частью числа и делает ввод нечитаемым. Таблица ниже зафиксирована на 24, 36 и 60 и не следует за введёнными числами: на ваши числа отвечает панель, а таблица показывает метод. Повторяющиеся числа допускаются и ничего не меняют. Ответ точный и никогда не округляется: все значения на этой странице — целые, далеко внутри диапазона, который машина хранит точно.

Как найти наибольший общий делитель вручную?

Выпишите делители каждого числа и возьмите наибольший из общих. Для 24, 36 и 60 эти списки сходятся на 12, значит наибольший общий делитель равен 12. Для больших чисел быстрее алгоритм Евклида: делите большее на меньшее, заменяете большее остатком и повторяете, пока остаток не станет нулём — для 1071 и 462 это четыре деления и ответ 21. Оба пути дают одно и то же число, и оба показаны в примерах выше.

Что значит, когда НОД равен 1?

Что числа взаимно простые, а это нормальный ответ, а не признак того, что что-то пошло не так. У 9 и 20 нет ни одного общего простого множителя, поэтому 1 — единственное число, которое делит оба. Так бывает часто: любые два последовательных целых числа взаимно просты, как и простое число в паре с числом, которое на него не делится. В этом случае список общих делителей приходит с единственной единицей.

Почему страница отклоняет 0 и отрицательные числа?

Потому что ответ зависел бы от соглашения, которого страница не заявляет. НОД(0, 5) во многих учебниках равен 5, а в других не определён; НОД(0, 0) в части изложений равен 0, а в остальных не определён вовсе. Отрицательные числа приносят отдельный набор правил знаков. Вместо того чтобы выбрать одно соглашение и молча его напечатать, страница просит целые числа от 1 и выше — там все источники согласны.

Как работает метод разложения на простые множители?

Разложите каждое число на простые множители, затем оставьте те простые числа, которые есть во всех числах, взяв наименьшую степень каждого. Для 24, 36 и 60 это 2² и 3, то есть 12. Наименьшая степень нужна потому, что делитель обязан делить каждое число списка: у 36 есть 3², а у 24 только одна 3, и вторая тройка сломала бы деление на 24. Для неудобных чисел разложение медленнее алгоритма Евклида, зато объясняет ответ.

Может ли ответ быть больше самого маленького числа в списке?

Нет. Общий делитель списка обязан делить самое маленькое число в нём, поэтому он никогда не превосходит это число, а до потолка доходит ровно тогда, когда самое маленькое число делит все остальные. Делитель пары 36 и 36 равен 36, а делитель 12, 24 и 36 равен 12. Меньше 1 он тоже не бывает: 1 делит любое целое число.

Где применяется наибольший общий делитель?

Чаще всего при сокращении дробей: разделив обе части 24/36 на 12, получаем 2/3 — то же значение с наименьшим возможным знаменателем. Приведение отношения к меньшим числам — тот же шаг: 24 : 36 : 60 — та же смесь, что 2 : 3 : 5. А взаимная простота двух чисел, то есть НОД, равный 1, — это условие, нужное нескольким результатам теории чисел, включая тот, на котором держится шифрование RSA.

• Greatest common divisor — the definition, the Euclidean algorithm, and the prime factorization method — Wolfram MathWorld (United States)
• Divisor — what it means for one whole number to divide another exactly, and how divisors are listed in pairs — Wolfram MathWorld (United States)
• Divisors of n arranged as a triangle — the sequence 1; 1, 2; 1, 3; 1, 2, 4; … that the divisor column of the table below is taken from, catalogued as OEIS A027750 — OEIS Foundation Inc. (United States)