MindCube Академия - Наименьшее общее кратное

Связь между НОД и НОК

Для любых двух натуральных чисел $a$ , $b$ верно следующее равенство:

$\textrm{НОД} (a; b) \cdot \textrm{НОК} (a; b) = ab.$

Доказательство

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

$\min(n;\,m)+\max(n;\, m)= n+m.$

Оно верно, т.к. $\min(n;\,m)$ совпадает с одним из чисел $n$ или $m$ , а $\max(n;\,m)$ с другим.

Запишем каноническое разложение на простые множители чисел $a$ и $b$ :

$a=p_1^{n_1} p_2^{n_2}\dots p_k^{n_k}\text{ и }b= p_1^{m_1} p_2^{m_2}\dots p_k^{m_k}$

(Возможно, что степени некоторых простых чисел равны нулю, то есть какое-то простое число присутствует в разложении одного из чисел $a$ или $b$ , но отсутствует в разложении другого.) Запишем теперь разложение $\textrm{HOД}(a,\;b)$ и $\textrm{НОК}(a,\;b)$ :

$\textrm{HOД}(a,\;b)= p_1^{\min\{n_1,\, m_1\}} p_2^{\min\{n_2,\,m_2\}}\dots p_k^{\min\{n_k,\,m_k\}}$

$\textrm{HOК}(a,\;b)= p_1^{\max\{n_1,\, m_1\}} p_2^{\max\{n_2,\,m_2\}}\dots p_k^{\max\{n_k,\,m_k\}}$

То есть

$\textrm{HOД}(a,\;b)\cdot\textrm{HOК}(a,\;b)=$

$= p_1^{\min\{n_1,\, m_1\}+\max\{n_1,\, m_1\}} p_2^{\min\{n_2,\, m_2\}+\max\{n_2,\,m_2\}}\dots p_k^{\min\{n_k,\, m_k\}+\max\{n_k,\,m_k\}}=$

в силу свойства, указанного в самом начале доказательства, получаем

$= p_1^{n_1+m_1} p_2^{ n_2+m_2}\dots p_k^{n_k+m_k}= \left(p_1^{n_1} p_2^{n_2}\dots p_k^{n_k}\right)\cdot (p_1^{m_1} p_2^{m_2}\dots p_k^{m_k})=ab.$

Теорема доказана.

Число $20$ является кратным как $4$ , так и $5$ . В таком случае говорят, что $20$ — это общее кратное чисел $4$ и $5$ .

Кратные числа $4$ : $4,\ 8,\ 12,\ 16,\ 20,\ 24,\ 28,\ 32,\ 36,\ 40,\ …$

Кратные числа $5$ : $5,\ 10,\ 15,\ 20,\ 25,\ 30,\ 35,\ 40,\ 45,\ 50,\ …$

Для чисел $4$ и $5$ общими кратными являются $20,\ 40,\ …$ , и наименьшее из них — это число $20$ .

Определение

Наименьшим общим кратным двух натуральных чисел называют такое наименьшее натуральное число, которое нацело делится на каждое из данных двух чисел.

Наименьшее общее кратное чисел $a$ и $b$ обозначают как $НОК (a;\ b)$ .

Например, $НОК (3;\ 4) = 12$ .

Нетрудно убедиться, что, например, $НОК (4;\ 5) = 20$ , $НОК (15;\ 20) = 60$ , $НОК (4;\ 16) = 16$ .

$\blacktriangleright$ Чтобы найти $НОК$ двух чисел, например, $12$ и $90$ , можно использовать следующий способ: последовательно выписывать числа, кратные $90$ , до тех пор, пока не получим число, кратное $12$ : $90$ , $180$ и так далее. Число $180$ является $НОК (12;\ 90)$ .

Часто для нахождения $НОК$ используют другой способ.

$\blacktriangleright$ Разложим на простые множители числа $18$ , $60$ и число $180$ , которое является их наименьшим общим кратным.

$18 = 2 \cdot 3 \cdot 3 = 2^1 \cdot 3^2$ ,

$60 = 2 \cdot 2 \cdot 3 \cdot 5 = 2^2 \cdot 3^1 \cdot 5^1$ ,

$180 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^2 \cdot 3^2 \cdot 5^1$ .

Заметим, что число $180$ , являющееся наименьшим общим кратным для $18$ и $60$ , включает множитель $3^2$ из разложения $18$ , а также $2^2$ и $5^1$ из разложения $60$ .

Алгоритм нахождения наименьшего общего кратного

	Шаги алгоритма	Например, найдём $НОК (120; 126)$
1	Разложить данные числа на простые множители.	$120=2\cdot 2\cdot 2\cdot 3\cdot 5=2^3\cdot 3^1\cdot 5^1,$ $126=2\cdot 3\cdot 3\cdot 7=2^1\cdot 3^2\cdot 7^1.$
2	В обоих разложениях из каждой пары степеней с одинаковыми основаниями выбрать степень с наибольшим показателем.	В нашем примере это $2^3$ и $3^2.$
3	Выбрать степени, основания которых встречаются только в одном из разложений.	В нашем примере это $5^1$ и $7^1.$
4	Перемножить выбранные степени; полученное произведение будет являться наименьшим общим кратным данной пары чисел.	$НОК (120; 126) = 2^3\cdot 3^2\cdot 5^1\cdot 7^1 = 2520.$

$\blacktriangleright$ Пример 1. Найдём $НОК(8;\ 15)$ .

$8 = 2 \cdot 2 \cdot 2 = 2^3$ ,

$15 = 3 \cdot 5 = 3^1 \cdot 5^1$ .

$НОК(8;\ 15) = 2^3 \cdot 3^1 \cdot 5^1 = 8 \cdot 15 = 120$ .

Числа $8$ и $15$ — взаимно простые, и наименьшее общее кратное таких чисел всегда равно их произведению.

$\blacktriangleright$ Пример 2. Найдём $НОК(150;\ 600)$ .

В данном случае можно обойтись без разложения на простые множители. Поскольку число $150$ является делителем числа $600$ , то:НОК(150; 600)=600.НОК(150;\ 600) = 600.НОК(150; 600)=600.

Если число $a$ — делитель числа $b$ , то $НОК(a;\ b)=b.$

Наименьшее общее кратное можно также находить для трёх и более чисел.

$\blacktriangleright$ Пример 3. Найдём $НОК (36;\ 48;\ 60)$ .

$36 = 2^2 \cdot 3^2$ ;

$48 = 2^4 \cdot 3^1$ ;

$60 = 2^2 \cdot 3^1 \cdot 5^1$ .

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

$НОК(36;\ 48;\ 60) = 2^4 \cdot 3^2 \cdot 5^1 = 720$ .