Перейти к содержимому

НОД: как найти наибольший общий делитель

Что означает НОД и как его найти: перебор, простые множители и алгоритм Евклида. Разбираем дроби, одинаковые группы, отличие от НОК и задачи с ответами.

10 мин чтения
Руслан Авдеев
Содержание статьи

НОД расшифровывается как «наибольший общий делитель». Для двух положительных натуральных чисел это самое большое натуральное число, на которое оба делятся без остатка. Например, НОД чисел 18 и 30 равен 6: получаются целые частные 3 и 5. Общий делитель находят перебором, через простые множители или алгоритмом Евклида. Он нужен для сокращения дробей и задач об одинаковых группах. В калькуляторе можно ввести два или три числа и разобрать решение по шагам.

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

Слово «делитель» показывает направление действия. Если 18 делится на 6 без остатка, то 6 — делитель числа 18. Если на то же число делится и 30, перед нами общий делитель пары. По материалам МЦНМО, наибольшим называют максимальный среди всех общих делителей.

Для 18 и 30 общий делитель 1 существует всегда, как и у любых двух положительных натуральных чисел. Есть также 2, 3 и 6. Самый большой в этом списке — 6. Запись НОД(18; 30) = 6 читают: «наибольший общий делитель восемнадцати и тридцати равен шести».

Вы нашли число 2, оба исходных числа на него делятся, и рука уже тянется закрыть тетрадь. Но задача просит наибольший общий делитель: двойка прошла отбор, а победителя ещё не выбрали. Такая проверка нужна, чтобы понимать смысл ответа, а не только выполнять деление.

В математических текстах встречаются обозначения НОД(a; b), gcd(a, b) и короткая запись (a, b). В школьном решении удобно пользоваться явной аббревиатурой НОД: её проще отличить от обычной пары чисел. Буквы a и b обозначают исходные числа.

Понятие Что проверяем Для 18 и 30
Делитель одного числа Делится ли выбранное число без остатка? 9 делит 18, но не делит 30
Общий делитель Делятся ли все исходные числа? 1, 2, 3 и 6
НОД Какой общий делитель максимален? 6

НОД положительных чисел не превосходит меньшего из них. Например, делитель 18 не может оказаться больше 18. Если меньшее число делит большее нацело, оно и будет НОД. Так, НОД(12; 48) = 12: искать дальше уже нечего.

Перебор делителей для небольших чисел

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

У 18 делители такие: 1, 2, 3, 6, 9 и 18. У 30: 1, 2, 3, 5, 6, 10, 15 и 30. Общие значения — 1, 2, 3, 6. Ответ получаем из их сравнения: НОД равен 6.

Пересечение делителей 18 и 30 содержит числа 1, 2, 3 и 6
В общей части находятся числа, которые делят и 18, и 30.

Чтобы не пропустить делитель, используйте пары. Для 18 произведения 1 × 18, 2 × 9 и 3 × 6 дают все пары натуральных множителей. Из каждой пары выписывают оба числа, затем располагают найденные значения по порядку.

Проверять кандидатов достаточно до квадратного корня: больший множитель появится в паре с меньшим. Например, для числа 18 граница — √18 ≈ 4,24: кандидата 4 ещё проверяем (4² = 16 < 18), а 5 уже за границей (5² = 25 > 18). Пары после этой границы начинают повторять уже найденные делители в обратном порядке.

Для устного вычисления можно идти иначе: проверить делители меньшего числа от большего к меньшему. У пары 18 и 30 сначала проверяют 18, затем 9, затем 6. Первое значение из такого убывающего списка, которое делит и второе число, даёт нужный ответ.

Для пары 13 и 20 общим делителем окажется только 1, и это полноценный математический ответ: такую пару называют взаимно простыми числами. Слово «взаимно» относится к паре. Например, 8 и 15 тоже взаимно простые, хотя каждое из них составное.

Как получить НОД через простые множители?

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

Рассмотрим 72 и 120. Получаем разложения: 72 = 2 × 2 × 2 × 3 × 3, а 120 = 2 × 2 × 2 × 3 × 5. В обеих строках есть три двойки и одна тройка. Их произведение равно 24.

Вторая тройка первой строки в результат не входит, поскольку во второй строке такого множителя нет; пятёрка тоже встречается только у одного числа. Поэтому НОД(72; 120) = 2 × 2 × 2 × 3 = 24. Проверка: 72 ÷ 24 = 3, 120 ÷ 24 = 5.

В разложениях 72 и 120 выделены три двойки и одна тройка, их произведение равно 24
Каждый общий множитель берут столько раз, сколько он присутствует в обеих строках.

При записи степенями правило выглядит компактнее: 72 = 2³ × 3², 120 = 2³ × 3 × 5. Для каждого общего простого числа выбирают меньший показатель степени. У двойки показатели одинаковы, у тройки выбираем 1. Получаем 2³ × 3 = 24.

Почему такой результат самый большой? Любой общий делитель состоит из простых множителей, которые должны поместиться в каждое разложение. Дополнительная тройка перестала бы делить 120, дополнительная двойка перестала бы делить 72. Мы использовали все общие возможности.

Полный список общих делителей можно получить и из найденного НОД. Для 72 и 120 он равен 24, поэтому общие делители — 1, 2, 3, 4, 6, 8, 12 и 24. Каждый из них делит 24, а значит, делит оба исходных числа. Обратно, любой общий делитель пары входит в делители её НОД. Это свойство позволяет восстановить всю общую часть без двух длинных списков.

  1. Разложите каждое число
    Запишите произведения простых множителей или степени.
  2. Сопоставьте повторения
    Для каждого простого числа найдите количество множителей, которое есть во всех разложениях.
  3. Перемножьте выбранное
    Полученный результат проверьте делением каждого исходного числа.

Алгоритм Евклида: цепочка остатков

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

Пусть a = b × q + r. Если число делит a и b, оно делит и r, потому что r = a − b × q. Обратно: общий делитель b и r делит сумму b × q + r, то есть a. Значит, у пар (a; b) и (b; r) одинаковые общие делители и одинаковый НОД.

Найдём НОД чисел 132 и 84. Сначала 132 = 84 × 1 + 48. Заменяем пару на 84 и 48. Затем 84 = 48 × 1 + 36. Дальше 48 = 36 × 1 + 12. Последнее деление: 36 = 12 × 3 + 0.

Остаток стал нулевым, поэтому процесс завершён. Последний ненулевой остаток — 12, это и есть НОД. В конечной паре 12 и 0 любое общее деление определяется числом 12. Исходные числа тоже делятся на него: 132 ÷ 12 = 11 и 84 ÷ 12 = 7.

Деления 132 на 84, 84 на 48, 48 на 36 и 36 на 12 завершаются нулевым остатком
Последний ненулевой остаток в цепочке равен 12.

Уже на первом шаге может получиться точное деление: например, для 48 и 12 имеем равенство 48 = 12 × 4 + 0. Ответ тогда равен делителю 12: искать предыдущий остаток не нужно. Эта деталь делает формулировку алгоритма полной и для кратных чисел.

Деление с остатком особенно выгодно, когда частное большое. Вместо сотни одинаковых вычитаний выполняется один переход. При этом причина сохранения ответа остаётся той же: общие делители исходной пары совпадают с общими делителями новой пары.

💡 История понятия

Евклид, работавший в Александрии около 300 года до н. э., описал нахождение общей меры в «Началах». В книге VII, предложении 2, задача решается через последовательное уменьшение чисел. Современная запись делениями с остатком выражает ту же математическую идею.

Источники: «Начала» Евклида, книга VII, предложение 2, публикация Clark University; исторический справочник MacTutor Университета Сент-Эндрюс.

Как найти общий делитель трёх чисел?

Определение сохраняется: искомое число должно делить каждое из исходных. При разложении выбирают множители, общие сразу для всех строк. Совпадения только в двух строках недостаточно, чтобы включить множитель в ответ.

Возьмём 24, 36 и 60. Разложения: 24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5. У всех есть две двойки и одна тройка. Их произведение равно 12. Проверяем: 24 ÷ 12 = 2, 36 ÷ 12 = 3, 60 ÷ 12 = 5.

Можно считать последовательно. Сначала НОД(24; 36) = 12, затем НОД(12; 60) = 12. Любой делитель всех трёх чисел обязан делить первые два, а значит, и их НОД. После добавления третьего числа остаются именно общие для всего набора делители.

Исходные числа НОД первых двух Следующий шаг Ответ
24, 36, 60 12 НОД(12; 60) 12
18, 30, 25 6 НОД(6; 25) 1
16, 32, 48 16 НОД(16; 48) 16

Вторая строка показывает важный случай. У первых двух чисел общий делитель 6, но третье на него не делится. Добавление числа может уменьшить результат. Поэтому ответ для части набора нужно проверить с оставшимися значениями.

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

Дроби и одинаковые отрезки

У дроби числитель и знаменатель можно разделить на один и тот же ненулевой общий делитель. Значение дроби сохранится. Если разделить их на НОД, получится несократимая дробь: общий множитель уже полностью убран.

Для 18/30 нашли НОД 6. Делим числитель и знаменатель: 18 ÷ 6 = 3, 30 ÷ 6 = 5. Получаем 3/5. Проверка обратным действием возвращает исходную дробь: 3 × 6 = 18, 5 × 6 = 30.

Можно было сначала сократить на 2, получить 9/15, затем ещё на 3. Ответ совпадёт, но использование НОД выполняет всё за один шаг. Для своей дроби есть калькулятор сокращения дробей, где можно проверить числитель, знаменатель и результат.

В задаче об отрезках НОД получает единицу длины. Даны ленты 84 см и 126 см; их нужно разрезать на одинаковые куски максимальной длины без обрезков. Длина каждого куска должна делить обе исходные длины. НОД(84; 126) = 42, поэтому подходят куски по 42 см.

Из первой ленты получится 84 ÷ 42 = 2 куска, из второй — 126 ÷ 42 = 3. Ответ на вопрос о длине — 42 см; число кусков находят последующим делением, поэтому эти две величины нужно различать.

Лис в мастерской придерживает ленту линейкой, рядом лежат ножницы и рулоны ткани
Для раскроя одинаковых кусков сначала определяют общую длину деления.

Если в условии вместо максимальной длины просят любой возможный размер, вариантов будет несколько. Например, длины 1, 2, 3, 6, 7, 14, 21 и 42 см делят обе ленты. Все они общие делители, но задача о максимальном размере выбирает один результат.

Сколько одинаковых наборов получится?

У задачи о наборах другой смысл ответа. Пусть есть 18 блокнотов и 30 карандашей. Нужно использовать всё и составить максимально много одинаковых наборов. Число наборов должно делить оба количества, поэтому оно равно НОД(18; 30) = 6.

Теперь найдём состав: в каждый набор войдут 18 ÷ 6 = 3 блокнота и 30 ÷ 6 = 5 карандашей. Проверка: 6 × 3 = 18 блокнотов, 6 × 5 = 30 карандашей. Условия об одинаковом составе и отсутствии остатка выполнены.

Вы раскладываете подарки по пакетам, а один карандаш остаётся на столе. Он пытается стать декорацией, но условие «без остатка» его не отпускает. Сначала проверьте число групп и их состав: оба вида предметов должны распределиться по одному правилу.

Лис и барсук готовят подарочные пакеты, на столе ещё лежат блокноты и карандаши
Одинаковый состав наборов требует общего деления всех запасов.

Здесь НОД обозначает количество наборов, а в предыдущем примере — длину куска. Одинаковое вычисление отвечает на разные вопросы. Подписывайте результат словами: «6 наборов», «42 см», «общий делитель 6».

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

В чём разница между НОД и НОК?

НОД делит исходные числа. НОК, наименьшее общее кратное, сам делится на каждое из них. Для 18 и 30 НОД равен 6, а НОК равен 90. Число 6 помещается в каждое исходное целое число раз; 90 содержит каждое из них целое число раз.

Признак НОД НОК
Направление делимости Делит исходные числа Делится на исходные числа
Для 18 и 30 6 90
Типичная задача Максимальное одинаковое деление без остатка Минимальная общая кратная величина
Дроби Сокращение Поиск общего знаменателя

Для двух положительных натуральных чисел выполняется связь: НОД(a; b) × НОК(a; b) = a × b. Проверим пару 18 и 30: 6 × 90 = 540, а 18 × 30 = 540. Формула даёт дополнительную проверку и позволяет найти НОК по уже известному НОД.

Для трёх чисел эту формулу так применять нельзя. Например, у 2, 3 и 6 НОД равен 1, НОК равен 6. Произведение НОД и НОК равно 6, а произведение исходных чисел — 36. Условия применимости формулы являются частью самого правила.

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

Выбор способа и проверка результата

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

У пары 35 и 64 разложения 5 × 7 и 2⁶ сразу показывают отсутствие общих простых множителей. Ответ — 1. У пары 132 и 84 деление с остатком быстро приводит к 12. Выбирайте способ по данным задачи и тому, что нужно показать в решении.

Как проверить ответ
  • Каждое исходное число делится на найденный результат без остатка.
  • В разложении использованы все допустимые общие множители либо цепочка Евклида завершена правильно.
  • Результат не больше меньшего исходного числа.
  • В текстовой задаче подписано, что именно обозначает найденное число.

Общий множитель иногда помогает уменьшить числа перед вычислением. У 72 и 120 можно вынести 6, получив 12 и 20. Их НОД равен 4, поэтому для исходной пары результат равен 6 × 4 = 24. Это следует из разложения: общий вынесенный множитель полностью входит в итоговый делитель.

Шесть заданий с ответами

Попробуйте для разных примеров выбрать разные способы. Один раз выпишите делители, в другом случае используйте разложения, затем проведите деление с остатком. После вычисления объясните ответ одной фразой своими словами.

1. Найдите НОД чисел 20 и 32.

Ответ: 4. Разложения 20 = 2² × 5 и 32 = 2⁵ дают общий множитель 2².

2. Чему равен НОД чисел 27 и 81?

Ответ: 27. Меньшее число делит большее: 81 ÷ 27 = 3.

3. Найдите НОД чисел 25 и 42.

Ответ: 1. В разложениях 5² и 2 × 3 × 7 нет общих простых множителей.

4. Сократите дробь 28/42 с помощью НОД.

Ответ: НОД(28; 42) = 14. Делим обе части на 14 и получаем 2/3.

5. Найдите НОД чисел 30, 45 и 75.

Ответ: 15. НОД(30; 45) = 15, а затем НОД(15; 75) = 15.

6. Ленты 60 и 84 см режут на одинаковые куски максимальной длины. Какова длина?

Ответ: НОД(60; 84) = 12, поэтому длина куска — 12 см. Получится 5 кусков из первой ленты и 7 из второй.

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

Ошибки, которые меняют ответ

Ошибка 1: остановиться на первом общем делителе

Почему так нельзя: найденное число может оказаться меньше нужного результата.

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

Ошибка 2: взять общие простые числа только по одному разу

Почему так нельзя: у 72 и 120 общий множитель 2 повторяется три раза. Если оставить одну двойку, получится 6 вместо 24.

Как не ошибиться: сопоставляйте количество повторений каждого простого множителя.

Ошибка 3: назвать ответом нулевой остаток

Почему так нельзя: ноль обозначает завершение цепочки, а делить исходные числа на ноль нельзя.

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

Ошибка 4: искать общие множители только у части набора

Почему так нельзя: результат должен делить каждое исходное число, включая третье.

Как не ошибиться: сравните все разложения или продолжите последовательный расчёт до последнего числа.

Ошибку в вычислениях удобно ловить обратной проверкой. Утверждение НОД(72; 120) = 30 сразу не проходит: 72 не делится на 30. Полезно также сверить исходные числа после переписывания: безошибочное решение для другой пары всё равно ответит на другой вопрос.

Вывод

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

Введите два или три числа, чтобы увидеть их разложения и шаги нахождения общего делителя.

Три вопроса к задаче
  • Что должно делиться без остатка?
  • Ищем длину части, число групп или множитель для сокращения?
  • Как проверить найденное значение обратным действием?

Часто задаваемые вопросы

Что такое НОД?

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

Чем НОД отличается от общего делителя?

Общих делителей может быть несколько. НОД — максимальный из них. Например, 2 и 3 делят и 18, и 30, но НОД этой пары равен 6.

Может ли НОД равняться одному?

Да. Такие числа называют взаимно простыми. Например, НОД(8; 15) = 1, хотя оба числа составные.

Как найти НОД разложением на множители?

Разложите каждое число на простые множители. Возьмите только общие множители с тем числом повторений, которое имеется во всех разложениях, и перемножьте их.

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

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

Какой НОД у двух одинаковых чисел?

Само это положительное число. Например, НОД(17; 17) = 17: каждый исходный член делится на 17, а больший делитель невозможен.

Чем НОД отличается от НОК?

НОД делит исходные числа, НОК сам делится на каждое из них. Для 18 и 30 получаем НОД 6 и НОК 90.

Зачем нужен НОД при сокращении дроби?

Деление числителя и знаменателя на их НОД сразу даёт несократимую дробь. Например, 18/30 после деления обеих частей на 6 превращается в 3/5.

Была ли статья полезной?

Одно нажатие, без регистрации. По ответам мы решаем, какие темы раскрывать подробнее.

Ваш ответ здесь будет первым.

Обсуждение

Комментарии читателей

Вопрос по статье, свой опыт или замеченная неточность — всё это помогает следующим читателям

Инструменты из этой статьи

Все статьи

Как складывать дроби — правило, примеры и частые ошибки

Чтобы сложить дроби, нужны одинаковые знаменатели: тогда складывают числители, а нижнее число оставляют прежним. Разные знаменатели приводят к общему через НОК. На примерах, чертежах и с калькулятором.

Инструкция6 мин чтения

Как умножать дроби — правило, примеры и частые ошибки

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

Инструкция6 мин чтения