Наибольший общий делитель
Наибольшее натуральное число, на которое делятся без остатка числа $a$ и $b$, называется наибольшим общим делителем и часто обозначается НОД.
Если натуральное число a делится на натуральное число $b$, то $b$ называют делителем числа $a$, а число $a$ называют кратным числа $b$.
Пусть $a$ и $b$-натуральные числа. Число $c$ называют общим делителем и для $a$ и для $b$.
Множество общих делителей чисел $a$ и $b$ конечно, так как ни один из этих делителей не может быть больше, чем $a$. Значит ,среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел $a$ и $b$ и для его обозначения используют записи :
$НОД \ (a;b) \ или \ D \ (a;b)$
Чтобы найти наибольший общий делитель двух, чисел необходимо:
- разложить числа на простые множители
- Выбрать числа, которые входят в разложение этих чисел
- Найти произведение чисел , найденных на шаге 2. Полученное число и будет искомым наибольшим общим делителем.
Найти НОД чисел $121$ и $132.$
Будем находить согласно представленному алгоритму. Для этого
-
разложить числа на простые множители
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
-
Выбрать числа, которые входят в разложение этих чисел
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
-
Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
$НОД=2\cdot 11=22$
Найти НОД одночленов $63$ и $81$.
Будем находить согласно представленному алгоритму. Для этого:
-
Разложим числа на простые множители
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
-
Выбираем числа, которые входят в разложение этих чисел
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
-
Найдем произведение чисел , найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
$НОД=3\cdot 3=9$
Найти НОД двух чисел можно и по-другому, используя множество делителей чисел.
Найти НОД чисел $48$ и $60$.
Решение:
Найдем множество делителей числа $48$: $\left\{{\rm 1,2,3.4.6,8,12,16,24,48}\right\}$
Теперь найдем множество делителей числа $60$:$\ \left\{{\rm 1,2,3,4,5,6,10,12,15,20,30,60}\right\}$
Найдем пересечение этих множеств: $\left\{{\rm 1,2,3,4,6,12}\right\}$- данное множество будет определять множество общих делителей чисел $48$ и $60$. Наибольший элемент в данном множестве будет число $12$. Значит наибольший общий делитель чисел $48$ и $60$ будет $12$.
$D(48;60)=12$
Определение НОК
Общим кратным натуральных чисел $a$ и $b$ называется натуральное число, которое кратно и $a$ и $b$.
Общими кратными чисел называются числа которые делятся на исходные без остатка.Например для чисел $25$ и $50$ общими кратными будут числа $50,100,150,200$ и т.д
Наименьшее из общих кратных будет называться наименьшим общим кратным и обозначается НОК$(a;b)$ или K$(a;b).$
Чтобы найти НОК двух чисел, необходимо:
- Разложить числа на простые множители
- Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого
- Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наименьшим общим кратным
Найти НОК чисел $99$ и $77$.
Будем находить согласно представленному алгоритму. Для этого
-
Разложить числа на простые множители
$99=3\cdot 3\cdot 11$
$77=7\cdot 11$
-
Выписать множители, входящие в состав первого
$3,3,11$
добавить к ним множители, которые входят в состав второго и не ходят в состав первого
$7$
-
Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наименьшим общим кратным
$НОК=3\cdot 3\cdot 11\cdot 7=693$
Составление списков делителей чисел часто очень трудоемкое занятие. Существует способ нахождение НОД, называемый алгоритмом Евклида.
Утверждения, на которых основан алгоритм Евклида:
-
Если $a$ и $b$ --натуральные числа, причем $a\vdots b$, то $D(a;b)=b$
Если $a$ и $b$ --натуральные числа, такие что $b
Пользуясь $D(a;b)= D(a-b;b)$, можно последовательно уменьшать рассматриваемые числа до тех пор, пока не дойдем до такой пары чисел, что одно из них делится на другое. Тогда меньшее из этих чисел и будет искомым наибольшим общим делителем для чисел $a$ и $b$.
Свойства НОД и НОК
- Любое общее кратное чисел $a$ и $b$ делится на K$(a;b)$
- Если $a\vdots b$ , то К$(a;b)=a$
-
Если К$(a;b)=k$ и $m$-натуральное число, то К$(am;bm)=km$
Если $d$-общий делитель для $a$ и $b$,то К($\frac{a}{d};\frac{b}{d}$)=$\ \frac{k}{d}$
-
Если $a\vdots c$ и $b\vdots c$ ,то $\frac{ab}{c}$ - общее кратное чисел $a$ и $b$
-
Для любых натуральных чисел $a$ и $b$ выполняется равенство
$D(a;b)\cdot К(a;b)=ab$
-
Любой общийй делитель чисел $a$ и $b$ является делителем числа $D(a;b)$
