3.9. НОД и НОК: наибольший общий делитель и наименьшее общее кратное
Рассмотрим такую задачу: найти делитель числа 140. Очевидно, что у числа 140 не один делитель, а несколько. В таких случаях говорят, что задача имеет множество решений. Найдем их все. Прежде всего разложим данное число на простые множители:
140 = 2 ∙ 2 ∙ 5 ∙ 7.
Теперь мы без труда можем выписать все делители. Начнем с простых делителей, то есть тех, которые присутствуют в разложении, приведенном выше:
Затем выпишем те, которые получаются попарным умножением простых делителей:
2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.
Затем — те, которые содержат в себе три простых делителя:
2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.
Наконец, не забудем единицу и само разлагаемое число:
Все найденные нами делители образуют множество делителей числа 140, которое записывается с помощью фигурных скобок:
Множество делителей числа 140 =
Для удобства восприятия мы выписали здесь делители (элементы множества) в порядке возрастания, но, вообще говоря, это делать необязательно. Кроме того, введем сокращение записи. Вместо «Множество делителей числа 140» будем писать «Д(140)». Таким образом,
Точно так же можно найти множество делителей для любого другого натурального числа. Например, из разложения
От множества всех делителей следует отличать множество простых делителей, которые для чисел 140 и 105 равны соответственно:
Следует особо подчеркнуть, что в разложении числа 140 на простые множители двойка присутствует два раза, в то время как во множестве ПД(140) — только один. Множество ПД(140) — это, по своей сути, все ответы на задачу: «Найти простой множитель числа 140». Ясно, что один и тот же ответ не следует повторять больше одного раза.
Сокращение дробей. Наибольший общий делитель
Мы знаем, что эту дробь можно сократить на такое число, которое одновременно является и делителем числителя (105) и делителем знаменателя (140). Взглянем на множества Д(105) и Д(140) и выпишем их общие элементы.
Общие элементы множеств Д(105) и Д(140) =
Последнее равенство можно записать короче, а именно:
Здесь специальный значок «∩» («мешок отверстием вниз») как раз и указывает на то, что из двух множеств, записанных по разные стороны от него, надо выбрать только общие элементы. Запись «Д(105) ∩ Д(140)» читается «пересечение множеств Дэ от 105 и Дэ от 140».
[Заметим по ходу дела, что с множествами можно производить разные бинарные операции, почти как с числами. Другой распространенной бинарной операцией является объединение, которое обозначается значком «∪» («мешок отверстием вверх»). В объединение двух множеств входят все элементы как того, так и другого множества:
Итак, мы выяснили, что дробь
можно сократить на любое из чисел, принадлежащих множеству
и нельзя сократить ни на какое другое натуральное число. Вот все возможные способы сокращения (за исключением неинтересного сокращения на единицу):
Очевидно, что практичнее всего сокращать дробь на число, по возможности большее. В данном случае это число 35, про которое говорят, что оно является наибольшим общим делителем (НОД) чисел 105 и 140. Это записывается как
Впрочем, на практике, если нам даны два числа и требуется найти их наибольший общий делитель, мы вовсе не должны строить какие-либо множества. Достаточно просто разложить оба числа на простые множители и подчеркнуть те из этих множителей, которые являются общими для обоих разложений, например:
Перемножая подчеркнутые числа (в любом из разложений), получаем:
Разумеется, возможен случай, когда подчеркнутых множителей окажется больше двух:
Отсюда видно, что
Особого упоминания заслуживает ситуация, когда общих множителей совсем нет и подчеркивать нечего, например:
Два натуральных числа, для которых НОД равен единице, называются взаимно простыми. Если из таких чисел составить дробь, например,
то такая дробь является несократимой.
Вообще говоря, правило сокращения дробей можно записать в таком виде:
Здесь предполагается, что a и b — натуральные числа, а вся дробь положительна. Если мы теперь припишем знак «минус» к обоим частям этого равенства, то получим соответствующее правило для отрицательных дробей.
Сложение и вычитание дробей. Наименьшее общее кратное
Пусть требуется вычислить сумму двух дробей:
Мы уже знаем, как раскладываются на простые множители знаменатели:
Из этого разложения сразу следует, что, для того чтобы привести дроби к общему знаменателю, достаточно числитель и знаменатель первой дроби умножить на 2 ∙ 2 (произведение неподчеркнутых простых множителей второго знаменателя), а числитель и знаменатель второй дроби — на 3 («произведение» неподчеркнутых простых множителей первого знаменателя). В результате знаменатели обеих дробей станут равны числу, которое можно представить так:
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.
Нетрудно видеть, что оба исходных знаменателя (как 105, так и 140) являются делителями числа 420, а число 420, в свою очередь, кратно обоим знаменателям, — и не просто кратно, оно является наименьшим общим кратным (НОК) чисел 105 и 140. Это записывается так:
НОК(105, 140) = 420.
Приглядевшись повнимательнее к разложению чисел 105 и 140, мы видим, что
105 ∙ 140 = НОК(105, 140) ∙ НОД(105, 140).
Точно так же, для произвольных натуральных чисел b и d: