Как найти НОД и НОК чисел

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

Общий делитель делит каждое из данных чисел без остатка. Для 12 и 18 общими делителями являются 1, 2, 3 и 6, поэтому НОД(12, 18) = 6. Наибольший общий делитель не может быть больше меньшего из положительных исходных чисел.

Общее кратное само делится на каждое исходное число. Для 12 и 18 первыми общими кратными будут 36, 72, 108 и далее, поэтому НОК(12, 18) = 36. Наименьшее общее кратное не меньше большего из положительных исходных чисел.

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

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

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

Важно сравнивать не только наличие множителя, но и количество повторений. Запись 72 = 2³ × 3² означает три множителя 2 и два множителя 3. Потерянная степень меняет результат, даже если набор простых чисел выглядит тем же.

• разложить каждое число до простых множителей
• для НОД выбрать общие множители с минимальными степенями
• для НОК выбрать все множители с максимальными степенями
• умножить и проверить делимость результата

Полный пример: НОД и НОК чисел 72 и 90

Разложим числа: 72 = 2³ × 3², а 90 = 2 × 3² × 5. Для НОД берём общие основания 2 и 3 с меньшими степенями: 2¹ × 3² = 18. Значит, НОД(72, 90) = 18.

Для НОК нужны все основания 2, 3 и 5 с большими степенями: 2³ × 3² × 5 = 360. Значит, НОК(72, 90) = 360. Проверка делением: 360 / 72 = 5 и 360 / 90 = 4, оба результата целые.

Есть дополнительная проверка для двух положительных чисел: НОД(a, b) × НОК(a, b) = a × b. Здесь 18 × 360 = 6480 и 72 × 90 = 6480. Равенство подтверждает согласованность двух ответов.

Как найти НОД алгоритмом Евклида

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

Найдём НОД(252, 198). Выполняем деление с остатком: 252 = 198 × 1 + 54; затем 198 = 54 × 3 + 36; затем 54 = 36 × 1 + 18; наконец 36 = 18 × 2 + 0. Последний ненулевой остаток равен 18.

После НОД легко получить НОК двух чисел: НОК(a, b) = |a × b| / НОД(a, b). Для 252 и 198 это 252 × 198 / 18 = 2772. Чтобы избежать громоздкого произведения, сначала удобно разделить одно число на НОД: 252 / 18 × 198.

НОД и НОК трёх и более чисел

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

Можно считать попарно: НОД(a, b, c) = НОД(НОД(a, b), c), а НОК(a, b, c) = НОК(НОК(a, b), c). Например, НОД(24, 36, 60): сначала НОД(24, 36) = 12, затем НОД(12, 60) = 12.

Формулу НОД × НОК = произведение исходных чисел нельзя напрямую переносить на три числа. Она в таком виде гарантированно работает для пары положительных чисел; для нескольких значений используйте разложение или последовательный попарный расчёт.

Типичные ошибки и проверка результата

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

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

• НОД не больше меньшего исходного числа
• НОК не меньше большего исходного числа
• каждое исходное число делит НОК без остатка
• для пары чисел произведения НОД и НОК равно произведению чисел