Наибольший общий делитель (НОД)

Как считается наибольший общий делитель (НОД)

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

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

• разделите большее число на меньшее и запомните остаток;
• поставьте на место большего числа делитель, а на место делителя — остаток;
• повторяйте деление, пока остаток не станет равен нулю;
• последний ненулевой остаток — это НОД.

Пример: найдём НОД(48, 18). Делим 48 на 18 — получаем 2 и остаток 12. Делим 18 на 12 — остаток 6. Делим 12 на 6 — остаток 0. Последний ненулевой остаток равен 6, значит НОД(48, 18) = 6. Калькулятор выше показывает эту цепочку делений целиком, так что ход решения можно переписать в тетрадь.

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

48 = 2⁴ × 3, 180 = 2² × 3² × 5 → НОД(48, 180) = 2² × 3 = 12

Если чисел больше двух, НОД находят цепочкой: сначала для первых двух чисел, потом НОД результата с третьим числом и так далее. Например, НОД(48, 18, 30): НОД(48, 18) = 6, затем НОД(6, 30) = 6 — это и есть ответ.

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

Два частных случая помогают проверить себя. Если у чисел нет общих делителей, кроме единицы — как у 8 и 15, — они называются взаимно простыми, и их НОД равен 1. А если одно число делится на другое нацело, НОД равен меньшему из них: НОД(7, 35) = 7. Знаки чисел на результат не влияют — НОД считают по модулям.

Зачем НОД нужен в школе

Главная задача — сокращение дробей. Чтобы сократить дробь до конца, числитель и знаменатель делят на их НОД. Возьмём дробь 48/180: НОД(48, 180) = 12, делим обе части на 12 и получаем 4/15. Дальше сокращать некуда — числа 4 и 15 взаимно простые. Если сокращать дробь по частям, легко остановиться на полпути и сдать работу с несокращённым ответом, а деление на НОД даёт окончательный вид за один шаг.

Где НОД пригождается в жизни

НОД отвечает на вопрос «на сколько одинаковых частей можно разделить разные вещи поровну». Есть 48 яблок и 36 груш, нужно разложить их в одинаковые подарочные наборы — максимум наборов равен НОД(48, 36) = 12, в каждом будет 4 яблока и 3 груши. Тот же приём помогает при раскрое ткани или доски без остатков, расстановке стульев рядами и разбивке класса на равные команды.

Как НОД связан с НОК

НОД и НОК — два полюса одной пары чисел, и между ними есть точная связь: произведение НОД и НОК равно произведению самих чисел:

НОД(a, b) × НОК(a, b) = a × b

Проверим на числах 48 и 180: НОД = 12, НОК = 720, и действительно 12 × 720 = 8640 = 48 × 180. Поэтому, найдя НОД алгоритмом Евклида, вы автоматически получаете и НОК — достаточно разделить произведение чисел на найденный делитель. Именно на этом равенстве работает наш калькулятор НОК.

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