Представьте: вы собираете гостей на день рождения. У вас 24 шоколадки и 36 конфет. Вы хотите разложить их в одинаковые подарочные пакеты так, чтобы в каждом было одно и то же количество шоколадок и одно и то же количество конфет — и ни одна конфета не осталась лишней. Сколько максимум пакетов получится? Ответ — 12, и найти его помогает один из самых древних математических инструментов: НОД и НОК.
НОД (наибольший общий делитель) — это самое большое число, на которое делятся без остатка два или несколько чисел. НОК (наименьшее общее кратное) — это самое маленькое число, которое делится без остатка на каждое из заданных чисел. Эти два понятия — близнецы: они всегда работают в паре и помогают решать задачи о ритмах, разбиении и согласовании.
💡 Любопытный факт. Алгоритм нахождения НОД, описанный Евклидом более 2300 лет назад, до сих пор используется в современных компьютерах. Его расширенная версия помогает решать задачи модульной арифметики, которые встречаются в криптографии, цифровых подписях и других вычислениях.
Пример из жизни: бумажные самолётики и две команды
В классе решили устроить соревнование по бумажным самолётикам. У Маши 18 листов бумаги, у Пети — 24 листа. Они хотят сделать одинаковые наборы для двух команд, чтобы в каждом наборе было одинаковое количество листов, а вся бумага ушла в дело. Сколько максимум наборов можно собрать?
Делители 18: 1, 2, 3, 6, 9, 18. Делители 24: 1, 2, 3, 4, 6, 8, 12, 24. Общие — 1, 2, 3, 6. Самый большой — 6. Значит, получится 6 наборов: в каждом будет по 3 листа Маши и по 4 листа Пети. Это и есть НОД(18, 24) = 6 — практический ответ на вопрос «как разделить честно и без остатка».
Что такое НОД и почему он важен
Когда мы говорим, что число делится на другое «без остатка», мы имеем в виду точное деление: 12 : 4 = 3, никаких хвостов. Числа, на которые наше число делится без остатка, называются его делителями. У числа 12 это 1, 2, 3, 4, 6, 12 — целая компания.
Если мы возьмём два числа, у них найдутся общие делители — те, на которые делятся оба. Среди общих делителей всегда есть самый большой — он и называется НОД. Записывают его так: НОД(12, 18) или (12, 18). Например, НОД(12, 18) = 6, потому что 6 — самое большое число, на которое делятся и 12, и 18.
Если у двух чисел НОД равен единице, их называют взаимно простыми. Например, 8 и 15 — взаимно простые: у них нет общих делителей, кроме единицы. Это важное свойство в теории чисел: оно используется во многих алгоритмах, включая некоторые криптографические схемы.
Что такое НОК и где он встречается
Если делители «смотрят внутрь» числа (что делит его на части), то кратные «смотрят наружу» — это всё, что получается умножением. Кратные числа 4 — это 4, 8, 12, 16, 20, 24… Кратные числа 6 — это 6, 12, 18, 24, 30… Общие кратные — 12, 24, 36… Самое маленькое из общих — 12. Это и есть НОК(4, 6) = 12.
НОК отвечает на вопрос «когда два процесса снова совпадут». Если автобус ходит каждые 4 минуты, а трамвай каждые 6 минут, и сейчас они оба у остановки — через сколько минут они снова окажутся вместе? Через 12. Это НОК их периодов.
Кстати, между НОД и НОК есть красивая связь. Для любых двух чисел a и b справедливо равенство: НОД(a, b) · НОК(a, b) = a · b. Если знаете одно, второе считается мгновенно. Например, НОД(12, 18) = 6, тогда НОК(12, 18) = 12 · 18 / 6 = 36. Удобно: одно вычисление вместо двух.
Три способа найти НОД
Способ 1. Перебор делителей
Простой и понятный метод: выписать все делители каждого числа, найти общие, выбрать самый большой. Работает для небольших чисел.
Пример. Найдём НОД(20, 30). Делители 20: 1, 2, 4, 5, 10, 20. Делители 30: 1, 2, 3, 5, 6, 10, 15, 30. Общие: 1, 2, 5, 10. Наибольший — 10. Значит, НОД(20, 30) = 10.
Минус: для больших чисел (вроде 348 и 504) перебирать делители вручную — занятие на полчаса. Поэтому придумали методы поумнее.
Способ 2. Разложение на простые множители
Любое натуральное число можно разложить на произведение простых: 12 = 2 · 2 · 3, 18 = 2 · 3 · 3. Из общих простых множителей берём наименьшие степени — это и есть НОД. Для НОК берём наибольшие степени всех встретившихся простых.
Пример. Найдём НОД и НОК для 60 и 84. Раскладываем:
- 60 = 2² · 3 · 5
- 84 = 2² · 3 · 7
Общие простые — 2 и 3. Минимальные степени: 2² и 3¹. Значит, НОД(60, 84) = 4 · 3 = 12. Для НОК берём все простые с максимальными степенями: 2² · 3 · 5 · 7 = 420. Проверим: 12 · 420 = 5040 = 60 · 84. ✓
Способ 3. Алгоритм Евклида — для больших чисел
Этот метод придумали более 2300 лет назад, а ничего быстрее до сих пор не изобрели. Идея гениально проста: НОД двух чисел равен НОД меньшего и остатка от деления большего на меньшее. Повторяем шаг, пока остаток не станет нулём. Последнее ненулевое число и есть ответ.
Пример. Найдём НОД(348, 504):
- 504 = 348 · 1 + 156
- 348 = 156 · 2 + 36
- 156 = 36 · 4 + 12
- 36 = 12 · 3 + 0 ← остаток ноль
Последний ненулевой остаток — 12. Значит, НОД(348, 504) = 12. Всего четыре шага деления вместо перебора десятков делителей! Именно такие алгоритмы работают внутри компьютера, когда он решает задачи с делимостью и модульной арифметикой.
Где НОД и НОК встречаются во взрослой жизни
Дроби. Чтобы сложить 5/12 и 7/18, нужен общий знаменатель — это НОК(12, 18) = 36. Без НОК ни одно действие с обыкновенными дробями не сделать. Каждый раз, складывая дроби, вы используете это понятие — пусть даже неосознанно.
Планирование производства. На фабрике один станок делает партию деталей за 15 минут, другой — за 20 минут, третий — за 12 минут. Когда они все одновременно закончат и можно будет менять заготовки? Через НОК(12, 15, 20) = 60 минут. Через час все три станка снова в синхроне — можно делать общий перерыв.
Криптография. В RSA и родственных задачах важны большие простые числа, взаимная простота и обратные элементы по модулю. Найти НОД компьютер может очень быстро, а разложить специально выбранное большое число на простые множители — гораздо сложнее. Поэтому алгоритм Евклида полезен как часть математического аппарата, но он не “шифрует PIN-код” напрямую.
Музыка и ритмы. Когда композитор накладывает один ритмический рисунок в 3 удара поверх другого в 4 удара, музыкальная фраза «закольцовывается» через НОК(3, 4) = 12 ударов. Полиритмия в африканской музыке и в композициях прогрессив-рока выстраивается именно на таких расчётах.
Попробуй сам
Три задачи на закрепление. Подумайте, попробуйте решить, а потом разверните спойлер.
Задача 1. У Кати 28 цветных карандашей, у Вани — 42. Они хотят разложить их в одинаковые пеналы так, чтобы во всех пеналах было поровну Катиных и поровну Ваниных карандашей. Какое максимальное число пеналов получится и сколько в каждом будет карандашей?
Показать решение
Нужно найти НОД(28, 42). Разложение: 28 = 2² · 7, 42 = 2 · 3 · 7. Общие — 2 и 7, минимальные степени 2¹ и 7¹. НОД = 14. Значит, получится 14 пеналов: в каждом по 2 карандаша Кати и по 3 карандаша Вани.
Задача 2. Колесо обозрения совершает полный оборот за 8 минут, карусель — за 6 минут. Сейчас они оба только что начали новый оборот. Через какое наименьшее время они снова одновременно окажутся в исходной точке?
Показать решение
Это задача на НОК. НОК(6, 8). Раскладываем: 6 = 2 · 3, 8 = 2³. Максимальные степени: 2³ и 3¹. НОК = 8 · 3 = 24 минуты. Через 24 минуты колесо сделает 3 полных оборота, а карусель — 4 оборота, и оба окажутся в точке старта.
Задача 3. Найдите НОД(126, 96) алгоритмом Евклида.
Показать решение
126 = 96 · 1 + 30
96 = 30 · 3 + 6
30 = 6 · 5 + 0
Последний ненулевой остаток — 6. Значит, НОД(126, 96) = 6.
История: от Евклида до криптографии
Понятия общего делителя и общего кратного появились ещё в Древней Греции. Евклид в седьмой книге «Начал» (около 300 г. до н. э.) описал процедуру нахождения наибольшего общего делителя двух чисел через последовательное вычитание — позже её упростили до деления с остатком, и алгоритм стал называться его именем. Это, возможно, самый старый из ныне используемых математических алгоритмов.
В XVII–XVIII веках алгоритм Евклида исследовали Этьен Безу и Карл Гаусс — они показали, что НОД двух чисел всегда можно представить в виде их линейной комбинации (тождество Безу), и это открыло путь к решению уравнений в целых числах. В XX веке, когда появилась криптография с открытым ключом, древний алгоритм неожиданно оказался одним из важных инструментов современной вычислительной математики.
Удивительный финал: НОД и музыка планет
Земля делает оборот вокруг Солнца за один год, Юпитер — примерно за 12 лет. Это значит, что раз в 12 лет они оказываются в одной и той же конфигурации относительно Солнца — НОК их периодов «обнуляет» взаимное положение. А ещё астрономы обнаружили, что многие пары планет движутся в так называемом орбитальном резонансе — когда их периоды относятся как небольшие целые числа. Например, у Юпитера и Сатурна резонанс 5:2, у Нептуна и Плутона — 3:2. Это означает, что через каждые НОК их «годов» планеты возвращаются в одно и то же взаимное расположение. По сути, Солнечная система — это гигантский часовой механизм, чьи стрелки тикают в ритме НОК.
Так что в следующий раз, складывая дроби или раскладывая конфеты по пакетам, помните: вы пользуетесь тем же математическим инструментом, который помогает описывать циклы, ритмы и некоторые вычисления в криптографии.
FAQ — частые вопросы
В чём разница между НОД и НОК простыми словами?
НОД — самое большое число, на которое делятся оба заданных числа. НОК — самое маленькое число, которое само делится на оба заданных. НОД ≤ любого из чисел, НОК ≥ любого из чисел.
Чему равен НОД для взаимно простых чисел?
Единице. Если НОД(a, b) = 1, числа называются взаимно простыми. Например, 9 и 16: общий делитель только 1. При этом НОК(9, 16) = 144 — произведение чисел.
Как быстро найти НОД для трёх чисел?
Используйте свойство ассоциативности: НОД(a, b, c) = НОД(НОД(a, b), c). Сначала находите НОД первых двух чисел, потом НОД результата и третьего. Так же и с НОК.
Может ли НОД быть больше одного из чисел?
Нет. НОД(a, b) ≤ min(a, b). Делитель числа не может быть больше самого числа. Если одно число делится на другое нацело, НОД равен меньшему: НОД(8, 24) = 8.
Зачем НОД и НОК нужны в реальной жизни, кроме школы?
В работе с дробями (общий знаменатель), в планировании циклических процессов (расписания, производство), в криптографии (RSA-шифрование, цифровые подписи), в кодах коррекции ошибок, в музыкальной теории и даже в астрономии при расчёте орбитальных резонансов планет.
Связь НОД и НОК в одной формуле
Для двух натуральных чисел работает полезная проверка: НОД(a, b) · НОК(a, b) = a · b. Например, для 12 и 18: НОД = 6, НОК = 36, поэтому 6 · 36 = 216 и 12 · 18 = 216.
Эта связь помогает проверять ответ после разложения на простые множители: если произведения не совпали, где-то потеряли множитель или взяли лишний.
Читайте также
- Признаки делимости: как за секунды понять, делится ли число
- Двоичная система счисления: как работает и где применяется
- Великая теорема Ферма: 358 лет ожидания и 129 страниц доказательства
- Евклид: математик, который написал учебник на 2300 лет вперёд
- Рамануджан: индийский математик-самоучка, обогнавший своё время
1 комментарий к “НОД и НОК: что это, формулы и 3 способа найти”