3.9. НОД и НОК: наибольший общий делитель и наименьшее общее кратное

Множество делителей

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

$140 = 2 \cdot 2 \cdot 5 \cdot 7$.

Теперь мы без труда можем выписать все делители. Начнем с простых делителей, то есть тех, которые присутствуют в разложении, приведенном выше:

$2, ~5, ~7$.

Затем выпишем те, которые получаются попарным умножением простых делителей:

$2\cdot 2 = 4, ~~~2\cdot 5 = 10, ~~~2\cdot 7 = 14, ~~~5\cdot 7 = 35$.

Затем — те, которые содержат в себе три простых делителя:

$2\cdot 2\cdot 5 = 20, ~~~2\cdot 2\cdot 7 = 28, ~~~2\cdot 5\cdot 7 = 70$.

Наконец, не забудем единицу и само разлагаемое число:

$1, ~140$.

Все найденные нами делители образуют множество делителей числа $140$, которое записывается с помощью фигурных скобок:

Множество делителей числа $140~=$

$\{1, ~2, ~4, ~5, ~7, ~10, ~14, ~20, ~28, ~35, ~70, ~140\}$.

Для удобства восприятия мы выписали здесь делители (элементы множества) в порядке возрастания, но, вообще говоря, это делать необязательно. Кроме того, введем сокращение записи. Вместо «Множество делителей числа $140$» будем писать «Д$(140)$» (читается «Дэ от $140$»). Таким образом,

Д$(140) = \{1, ~2, ~4, ~5, ~7, ~10, ~14, ~20, ~28, ~35, ~70, ~140\}$.

Точно так же можно найти множество делителей для любого другого натурального числа. Например, из разложения

$105 = 3 \cdot 5 \cdot 7$

мы получаем:

Д$(105) = \{1, ~3, ~5, ~7, ~15, ~21, ~35, ~105\}$.

От множества всех делителей следует отличать множество простых делителей, которые для чисел $140$ и $105$ равны соответственно:

ПД$(140) = \{2, ~5, ~7\}$.

ПД$(105) = \{3, ~5, ~7\}$.

Следует особо подчеркнуть, что в разложении числа $140$ на простые множители двойка присутствует два раза, в то время как во множестве ПД$(140)$ — только один. Множество ПД$(140)$ — это, по своей сути, все ответы на задачу: «Найти простой множитель числа $140$». Ясно, что один и тот же ответ не следует повторять больше одного раза.

Сокращение дробей. Наибольший общий делитель

Рассмотрим дробь

$\dfrac{105}{140}$.

Мы знаем, что эту дробь можно сократить на такое число, которое одновременно является и делителем числителя ($105$) и делителем знаменателя ($140$). Взглянем на множества Д$(105)$ и Д$(140)$ и выпишем их общие элементы.

 

Д$(105) = \{1, ~3, ~5, ~7, ~15, ~21, ~35, ~105\}$;

Д$(140) = \{1, ~2, ~4, ~5, ~7, ~10, ~14, ~20, ~28, ~35, ~70, ~140\}$.

 

Общие элементы множеств Д$(105)$ и Д$(140)~=$

$\{1, ~5, ~7, ~35\}$.

 

Последнее равенство можно записать короче, а именно:

Д$(105)~\cap~$Д$(140)~=~\{1, ~5, ~7, ~35\}$.

Здесь специальный значок «$\cap$» («мешок отверстием вниз») как раз и указывает на то, что из двух множеств, записанных по разные стороны от него, надо выбрать только общие элементы. Запись «Д$(105)~\cap~$Д$(140)$» читается «пересечение множеств Дэ от $105$ и Дэ от $140$».

Замечание. Отметим по ходу дела, что с множествами можно производить разные бинарные операции, почти как с числами. Другой распространенной бинарной операцией является объединение, которое обозначается значком «$\cup$» («мешок отверстием вверх»). В объединение двух множеств входят все элементы как того, так и другого множества:

ПД$(105) = \{3, ~5, ~7\}$;

ПД$(140) = \{2, ~5, ~7\}$;

ПД$(105)~\cup~$ПД$(140) = \{2, ~3, ~5, ~7\}$.

Итак, мы выяснили, что дробь

$\dfrac{105}{140}$

можно сократить на любое из чисел, принадлежащих множеству

Д$(105)~\cap~$Д$(140) = \{1, ~5, ~7, ~35\}$

и нельзя сократить ни на какое другое натуральное число. Вот все возможные способы сокращения (за исключением неинтересного сокращения на единицу):

$\begin{align} &\frac{105}{140} = \frac{105/5}{140/5} = \frac{21}{28},\\ &\frac{105}{140} = \frac{105/7}{140/7} = \frac{15}{20},\\ &\frac{105}{140} = \frac{105/35}{140/35} = \frac{\,3\,}{4}. \end{align}$

Очевидно, что практичнее всего сокращать дробь на число, по возможности большее. В данном случае это число $35$, про которое говорят, что оно является наибольшим общим делителем (НОД) чисел $105$ и $140$. Это записывается как

НОД$(105, ~140) = 35$.

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

$105 = 3 \cdot \underline{\,5\,} \cdot \underline{\,7\,}$;

$140 = 2 \cdot 2 \cdot \underline{\,5\,} \cdot \underline{\,7\,}$.

Перемножая подчеркнутые числа (в любом из разложений), получаем:

НОД$(105, ~140) = 5 \cdot 7 = 35$.

Разумеется, возможен случай, когда подчеркнутых множителей окажется больше двух:

$168 = \underline{\,2\,} \cdot \underline{\,2\,} \cdot 2 \cdot \underline{\,3\,} \cdot 7$;

$396 = \underline{\,2\,} \cdot \underline{\,2\,} \cdot \underline{\,3\,} \cdot 3 \cdot 11$.

Отсюда видно, что

НОД$(168, ~396) = \underline{\,2\,} \cdot \underline{\,2\,} \cdot \underline{\,3\,} = 12$.

Особого упоминания заслуживает ситуация, когда общих множителей совсем нет и подчеркивать нечего, например:

$42 = 2 \cdot 3 \cdot 7$;

$55 = 5 \cdot 11$.

В этом случае,

НОД$(42, \,55) = 1$.

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

$\dfrac{42}{55}$,

то такая дробь является несократимой.

Вообще говоря, правило сокращения дробей можно записать в таком виде:

$\dfrac{\,a\,}{b} = \dfrac{a/\text{НОД}(a, b)}{b/\text{НОД}(a, b)}\,$.

Здесь предполагается, что $a$ и $b$ — натуральные числа, а вся дробь положительна. Если мы теперь припишем знак «минус» к обоим частям этого равенства, то получим соответствующее правило для отрицательных дробей.

Сложение и вычитание дробей. Наименьшее общее кратное

Пусть требуется вычислить сумму двух дробей:

$\dfrac{1}{105} + \dfrac{1}{140}$.

Мы уже знаем, как раскладываются на простые множители знаменатели:

$105 = 3 \cdot \underline{\,5\,} \cdot \underline{\,7\,}$;

$140 = 2 \cdot 2 \cdot \underline{\,5\,} \cdot \underline{\,7\,}$.

Из этого разложения сразу следует, что, для того чтобы привести дроби к общему знаменателю, достаточно числитель и знаменатель первой дроби умножить на $2 \cdot 2$ (произведение неподчеркнутых простых множителей второго знаменателя), а числитель и знаменатель второй дроби — на $3$ («произведение» неподчеркнутых простых множителей первого знаменателя). В результате знаменатели обеих дробей станут равны числу, которое можно представить так:

Нетрудно видеть, что оба исходных знаменателя (как $105$, так и $140$) являются делителями числа $420$, а число $420$, в свою очередь, кратно обоим знаменателям, — и не просто кратно, оно является наименьшим общим кратным (НОК) чисел $105$ и $140$. Это записывается так:

НОК$(105, ~140) = 420$.

Итак, чтобы получить НОК чисел $105$ и $140$, мы разложили их на простые множители, подчеркнули те множители, которые являются общими для обоих чисел, а далее написали:

НОК $=$ все множители первого числа $\times$ неподчеркнутые множители второго числа.

Отсюда следует, что

НОК$(105, 140) = 105 \cdot 140 /~$НОД$(105, 140)$.

Это можно также переписать в несколько более изящной, «симметричной» форме:

$105 \cdot 140~=~$НОК$(105, 140)~\cdot~$НОД$(105, 140)$.

Точно так же, для произвольных натуральных чисел $b$ и $d$:

$b \cdot d~=~$НОК$(b, d)~\cdot~$НОД$(b, d)$.

Теперь давайте доведем до конца суммирование наших дробей:

$\begin{align} &\dfrac{1}{105} + \dfrac{1}{140} =\\[2mm] &= \dfrac{1}{3 \cdot \underline{\,5\,} \cdot \underline{\,7\,}} + \frac{1}{2 \cdot 2 \cdot \underline{\,5\,} \cdot \underline{\,7\,}} =\\[2mm] &= \dfrac{2 \cdot 2 }{2 \cdot 2 \cdot 3 \cdot \underline{\,5\,} \cdot \underline{\,7\,}} + \dfrac{3}{3 \cdot 2 \cdot 2 \cdot \underline{\,5\,} \cdot \underline{\,7\,}} =\\[2mm] &= \dfrac{4 + 3}{2 \cdot 2 \cdot 3 \cdot \underline{\,5\,} \cdot \underline{\,7\,}} = \dfrac{7}{2 \cdot 2 \cdot 3 \cdot \underline{\,5\,} \cdot \underline{\,7\,}} = \dfrac{1}{2 \cdot 2 \cdot 3 \cdot \underline{\,5\,}} = \dfrac{1}{60}\,. \end{align}$

Подобным же образом можно посчитать разность:

$\dfrac{1}{105} - \dfrac{1}{140} = \dfrac{4}{4 \cdot 105} - \dfrac{3}{3 \cdot 140} = \dfrac{4}{420} - \dfrac{3}{420} = \dfrac{1}{420}$.

Для того чтобы получить общий знаменатель двух дробей $\frac{\,a\,}{b}$ и $\frac{\,c\,}{d}$, мы фактически проделываем ту же самую процедуру, что и при вычислении НОК$(b, d)$. Именно НОК$(b, d)$ и оказывается общим знаменателем. (Предполагается, что $a$, $b$, $c$ и $d$ — натуральные числа.)

Конспект

1. Правило сокращения дробей. Пусть $a$ и $b$ — натуральные числа (${b \ne 0}$). Тогда

$\dfrac{\,a\,}{b} = \dfrac{a/\text{НОД}(a, b)}{b/\text{НОД}(a, b)}$ ,

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

2. Приведение дробей к общему знаменателю. Пусть $\,a$, $\,b$, $\,c$ и $\,d$ — натуральные числа (${b \ne 0}$, ${\,d \ne 0}$). В качестве общего знаменателя двух дробей $\frac{\,a\,}{b}$ и $\frac{\,c\,}{d}$ удобно брать НОК$(b, d)$ — наименьшее общее кратное знаменателей $b$ и $d$. Чтобы получить НОК$(b, d)$, мы раскладываем числа $b$ и $d$ на простые множители, причем общие множители подчеркиваем. Тогда

НОК $=$ все множители числа $b~\times$ неподчеркнутые множители числа $d$.

3. НОК и НОД связаны соотношением

$b \cdot d = \text{НОК}(b, d) \cdot \text{НОД}(b, d)$.

Из «бесконечного» сборника типовых упражнений

Задачи, где требуется разлагать числа на простые множители

Примечание. Для решения некоторых задач требуется знать, что такое квадрат числа. Квадратом числа $a$ называется число $a$, помноженное само на себя, то есть $a \cdot a$. (Оно называется так, потому что равно площади квадрата со стороной $a$).