§ 13. Наибольший общий делитель и наименьшее общее кратное двух целых чисел

Определения и обозначения

Делитель целого числа — целое число, на которое данное число делится без остатка. Например, 3 и −3 — делители числа 12, потому что 12 : 3 = 4 и 12 : (−3) = −4. У любого ненулевого числа есть как положительные, так и отрицательные делители. Это понятие помогает выяснить, на какие равные части можно разделить число без остатка.

Общий делитель двух целых чисел — число, которое делит каждое из них без остатка. Например, 2 — общий делитель чисел 18 и 30: оба числа делятся на 2. Общих делителей может быть несколько. Их поиск показывает, какие числа подходят одновременно для обоих исходных чисел.

Наибольший общий делитель (НОД) — наибольший положительный общий делитель двух чисел. Его обозначают НОД(a, b) или (a, b). Например, у чисел 18 и 30 НОД равен 6. НОД нужен, когда требуется найти самый большой общий делитель, например для сокращения дроби.

Наименьшее общее кратное (НОК) — наименьшее положительное число, кратное обоим данным числам. Его обозначают НОК(a, b) или [a, b]. Например, 90 — наименьшее число, которое делится и на 18, и на 30. НОК помогает найти ближайшее общее кратное, в частности общий знаменатель дробей.

Как это устроено

При поиске НОД достаточно рассматривать положительные делители. Если отрицательное число делит данное число, то и противоположное ему положительное число тоже является делителем: например, вместе с −4 делителем будет 4. Поэтому отрицательное число не может быть наибольшим положительным делителем, и оно не влияет на выбор НОД.

Делимость и кратность описывают одну связь с разных сторон. Если d — общий делитель a и b, то a и b делятся на d без остатка. Если же m — общее кратное a и b, то m делится на каждое из этих чисел. Поэтому НОД ищут среди общих делителей, а НОК — среди чисел, кратных обоим исходным.

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

Связь НОД и НОК можно увидеть по простым множителям. Для каждого простого множителя показатель в НОД равен меньшему из показателей исходных чисел, а в НОК — большему. Сумма меньшего и большего показателей равна сумме исходных, поэтому произведение НОД на НОК совпадает с произведением модулей чисел: НОД(a, b) · НОК(a, b) = |ab|. Отсюда НОК(a, b) = |ab| / НОД(a, b), если числа ненулевые.

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

НОД и НОК двух целых чисел

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

Разбор задач

Задача 1. Найти НОД(18, 30) и НОК(18, 30). Здесь удобно разложить оба числа на простые множители: общие множители определят НОД, а все необходимые для делимости множители — НОК. Сначала запишем разложения и сравним показатели одинаковых простых чисел. Затем проверим найденные значения делимостью и формулой связи.

1. Разложим числа: 18 = 2 · 3², 30 = 2 · 3 · 5.
2. Общие простые множители — 2 и 3. Для НОД берём меньшие показатели: 2¹ · 3¹ = 6.
3. Для НОК берём все множители с наибольшими показателями: 2¹ · 3² · 5¹ = 90.
4. Проверим: 90 : 18 = 5, 90 : 30 = 3; также 6 · 90 = 540 = 18 · 30.

Ответ: НОД(18, 30) = 6, НОК(18, 30) = 90.

Задача 2. Найти НОД(252, 198) алгоритмом Евклида. Вместо разложения больших чисел будем делить с остатком. Каждый раз заменяем пару большим числом и меньшим остатком: общий делитель при такой замене сохраняется. Остановимся, когда остаток станет нулём.

1. Делим 252 на 198: 252 = 198 · 1 + 54.
2. Заменяем пару на 198 и 54: 198 = 54 · 3 + 36.
3. Продолжаем: 54 = 36 · 1 + 18.
4. Делим дальше: 36 = 18 · 2 + 0. Последний ненулевой остаток равен 18.

Ответ: НОД(252, 198) = 18. Проверка показывает, что 252 и 198 делятся на 18 без остатка.

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

1. Запишем формулу: НОД(a, b) · НОК(a, b) = |ab|.
2. Подставим известные значения: 12 · НОК(a, b) = 3600.
3. Разделим обе части на 12: НОК(a, b) = 3600 : 12 = 300.

Ответ: НОК равен 300.

Типичные ошибки

Ошибка: считать отрицательное число наибольшим общим делителем. Так бывает, если забыть, что НОД по определению положительный; отрицательные делители действительно существуют, но не могут быть ответом. Проверь знак результата: НОД должен быть больше нуля. Например, для чисел 12 и 18 ответом будет 6, а не −6.

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

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

Ошибка: применять равенство НОД(a, b) · НОК(a, b) = ab к отрицательным числам без учёта знака. Если произведение a и b отрицательно, произведение двух положительных величин НОД и НОК не может быть ему равно. Для целых чисел в формуле используют модуль: НОД(a, b) · НОК(a, b) = |ab|. Перед вычислением проверь знаки исходных чисел и возьми модуль их произведения.

Связь с другими темами

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

Что запомнить

• НОД — наибольший положительный общий делитель.
• НОК — наименьшее положительное общее кратное.
• Для НОД при разложении на простые множители берут общие множители с наименьшими показателями.
• Для НОК берут все простые множители с наибольшими показателями.
• Для ненулевых целых a и b: НОД(a, b) · НОК(a, b) = |ab|.
• Алгоритм Евклида позволяет находить НОД последовательным делением с остатком.