НОД и НОК двух чисел, алгоритм Евклида

Источник статьи

Автор24 — учеба по твоим правилам

Наибольший общий делитель

Определение 1

Наибольшее натуральное число, на которое делятся без остатка числа $a$ и $b$ , называется наибольшим общим делителем и часто обозначается НОД.

Определение 2

Если натуральное число a делится на натуральное число $b$ , то $b$ называют делителем числа $a$ , а число $a$ называют кратным числа $b$ .

Пусть $a$ и $b$ -натуральные числа. Число $c$ называют общим делителем и для $a$ и для $b$ .

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

$НОД \ (a;b) \ или \ D \ (a;b)$

Чтобы найти наибольший общий делитель двух, чисел необходимо:

разложить числа на простые множители
Выбрать числа, которые входят в разложение этих чисел
Найти произведение чисел , найденных на шаге 2. Полученное число и будет искомым наибольшим общим делителем.

Пример 1

Найти НОД чисел $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$

Пример 2

Найти НОД одночленов $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$

«НОД и НОК двух чисел, алгоритм Евклида» 👇

Помощь эксперта по теме работы

Найти эксперта

Решение задач от ИИ за 2 минуты

Решить задачу

Найди решение своей задачи среди 1 000 000 ответов

Найти

Найти НОД двух чисел можно и по-другому, используя множество делителей чисел.

Пример 3

Найти НОД чисел $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$

Определение НОК

Определение 3

Общим кратным натуральных чисел $a$ и $b$ называется натуральное число, которое кратно и $a$ и $b$ .

Общими кратными чисел называются числа которые делятся на исходные без остатка.Например для чисел $25$ и $50$ общими кратными будут числа $50,100,150,200$ и т.д

Наименьшее из общих кратных будет называться наименьшим общим кратным и обозначается НОК $(a;b)$ или K $(a;b).$

Чтобы найти НОК двух чисел, необходимо:

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

Пример 4

Найти НОК чисел $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)$