Разместить заказ
Вы будете перенаправлены на Автор24

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

8-800-775-03-30 support@author24.ru
Все предметы / Математика / Делимость чисел / НОД и НОК двух чисел, алгоритм Евклида

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

Определение 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)$

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

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

Найти НОД чисел $121$ и $132.$

Будем находить согласно представленному алгоритму. Для этого

  1. разложить числа на простые множители

    $242=2\cdot 11\cdot 11$

    $132=2\cdot 2\cdot 3\cdot 11$

  2. Выбрать числа, которые входят в разложение этих чисел

    $242=2\cdot 11\cdot 11$

    $132=2\cdot 2\cdot 3\cdot 11$

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

    $НОД=2\cdot 11=22$

Пример 2

Найти НОД одночленов $63$ и $81$.

Будем находить согласно представленному алгоритму. Для этого:

  1. Разложим числа на простые множители

    $63=3\cdot 3\cdot 7$

    $81=3\cdot 3\cdot 3\cdot 3$

  2. Выбираем числа, которые входят в разложение этих чисел

    $63=3\cdot 3\cdot 7$

    $81=3\cdot 3\cdot 3\cdot 3$

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

    $НОД=3\cdot 3=9$

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

Пример 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).$

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

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

Найти НОК чисел $99$ и $77$.

Будем находить согласно представленному алгоритму. Для этого

  1. Разложить числа на простые множители

    $99=3\cdot 3\cdot 11$

    $77=7\cdot 11$

  2. Выписать множители, входящие в состав первого

    $3,3,11$

    добавить к ним множители, которые входят в состав второго и не ходят в состав первого

    $7$

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

    $НОК=3\cdot 3\cdot 11\cdot 7=693$

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

    Утверждения, на которых основан алгоритм Евклида:

  4. Если $a$ и $b$ --натуральные числа, причем $a\vdots b$, то $D(a;b)=b$

  5. Если $a$ и $b$ --натуральные числа, такие что $b

Пользуясь $D(a;b)= D(a-b;b)$, можно последовательно уменьшать рассматриваемые числа до тех пор, пока не дойдем до такой пары чисел, что одно из них делится на другое. Тогда меньшее из этих чисел и будет искомым наибольшим общим делителем для чисел $a$ и $b$.

Свойства НОД и НОК

  1. Любое общее кратное чисел $a$ и $b$ делится на K$(a;b)$
  2. Если $a\vdots b$ , то К$(a;b)=a$
  3. Если К$(a;b)=k$ и $m$-натуральное число, то К$(am;bm)=km$

    Если $d$-общий делитель для $a$ и $b$,то К($\frac{a}{d};\frac{b}{d}$)=$\ \frac{k}{d}$

  4. Если $a\vdots c$ и $b\vdots c$ ,то $\frac{ab}{c}$ - общее кратное чисел $a$ и $b$

  5. Для любых натуральных чисел $a$ и $b$ выполняется равенство

    $D(a;b)\cdot К(a;b)=ab$

  6. Любой общийй делитель чисел $a$ и $b$ является делителем числа $D(a;b)$

Статья предоставлена специалистами сервиса Автор24
Автор24 - это сообщество учителей и преподавателей, к которым можно обратиться за помощью с выполнением учебных работ.
как работает сервис