Нахождение нод и нок правило. Наименьшее общее кратное (НОК) – определение, примеры и свойства

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

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

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

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

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

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

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

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

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

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

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

Пример 4

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

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

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

$99=3\cdot 3\cdot 11$

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

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

Найти произведение чисел, найденных на шаге 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)$

Признаки делимости натуральных чисел.

Числа, делящиеся без остатка на 2, называются четными .

Числа, которые не делятся без остатка на 2, называются нечетными .

Признак делимости на 2

Если запись натурального числа оканчивается четной цифрой, то это число делится без остатка на 2, а если запись числа оканчивается нечетной цифрой, то это число не делится без остатка на 2.

Например, числа 6 0 , 30 8 , 8 4 делятся без остатка на 2, а числа 5 1 , 8 5 , 16 7 не делятся без остатка на 2.

Признак делимости на 3

Если сумма цифр числа делится на 3, то и число делится на 3; если сумма цифр числа не делится на 3, то и число не делится на 3.

Например, выясним, делится ли на 3 число 2772825. Для этого подсчитаем сумму цифр этого числа: 2+7+7+2+8+2+5 = 33 - делится на 3. Значит, число 2772825 делится на 3.

Признак делимости на 5

Если запись натурального числа оканчивается цифрой 0 или 5, то это число делится без остатка на 5. Если же запись числа оканчивается иной цифрой, то число без остатка на 5 не делится.

Например, числа 1 5 , 3 0 , 176 5 , 47530 0 делятся без остатка на 5, а числа 1 7 , 37 8 , 9 1 не делятся.

Признак делимости на 9

Если сумма цифр числа делится на 9, то и число делится на 9; если сумма цифр числа не делится на 9, то и число не делится на 9.

Например, выясним, делится ли на 9 число 5402070. Для этого подсчитаем сумму цифр этого числа: 5+4+0+2+0+7+0 = 16 - не делится на 9. Значит, число 5402070 не делится на 9.

Признак делимости на 10

Если запись натурального числа оканчивается цифрой 0, то это число делится без остатка на 10. Если запись натурального числа оканчивается другой цифрой, то оно не делится без остатка на 10.

Например, числа 4 0 , 17 0 , 1409 0 делятся без остатка на 10, а числа 1 7 , 9 3 , 1430 7 - не делятся.

Правило нахождения наибольшего общего делителя (НОД).

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

2) из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел;

3) найти произведение оставшихся множителей.

Пример. Найдем НОД (48;36). Воспользуемся правилом.

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

48 = 2 · 2 · 2 · 2 · 3

36 = 2 · 2 · 3 · 3

2. Из множителей, входящих в разложение числа 48 вычеркнем те, которые не входят в разложение числа 36.

48 = 2 · 2 · 2 · 2 · 3

Остаются множители 2, 2 и 3.

3. Перемножим оставшиеся множители и получим 12. Это число и является наибольшим общим делителем чисел 48 и 36.

НОД (48;36) = 2 · 2 · 3 = 12.

Правило нахождения наименьшего общего кратного (НОК).

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

1) разложить их на простые множители;

2) выписать множители, входящие в разложение одного из чисел;

3) добавить к ним недостающие множители из разложений остальных чисел;

4) найти произведение получившихся множителей.

Пример. Найдем НОК (75;60). Воспользуемся правилом.

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

75 = 3 · 5 · 5

60 = 2 · 2 · 3 · 3

2. Выпишем множители, входящие в разложение числа 75: 3, 5, 5.

НОК (75;60) = 3 · 5 · 5 · …

3. Добавим к ним недостающие множители из разложения числа 60, т.е. 2, 2.

НОК (75;60) = 3 · 5 · 5 · 2 · 2

4. Найдем произведение получившихся множителей

НОК (75;60) = 3 · 5 · 5 · 2 · 2 = 300.

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

Теперь мы можем дать определение наибольшего общего делителя двух чисел.

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

Наибольший общий делитель двух целых чисел – это наибольшее целое число, делящее два данных целых числа.

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

Приведем пример наибольшего общего делителя (НОД) двух целых чисел. Наибольший общий делитель чисел 6 и −15 равен 3 . Обоснуем это. Запишем все делители числа шесть: ±6 , ±3 , ±1 , а делителями числа −15 являются числа ±15 , ±5 , ±3 и ±1 . Теперь можно найти все общие делители чисел 6 и −15 , это числа −3 , −1 , 1 и 3 . Так как −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

Определение наибольшего общего делителя трех и большего количества целых чисел аналогично определению НОД двух чисел.

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

Наибольший общий делитель трех и большего количества целых чисел – это наибольшее целое число, делящее одновременно все данные числа.

Наибольший общий делитель n целых чисел a 1 , a 2 , …, a n мы будем обозначать как НОД(a 1 , a 2 , …, a n) . Если найдено значение b наибольшего общего делителя этих чисел, то можно записать НОД(a 1 , a 2 , …, a n)=b .

В качестве примера приведем НОД четырех целых чисел −8 , 52 , 16 и −12 , он равен 4 , то есть, НОД(−8, 52, 16, −12)=4 . Это можно проверить, записав все делители данных чисел, выбрав из них общие и определив наибольший общий делитель.

Отметим, что наибольший общий делитель целых чисел может быть равен одному из этих чисел. Это утверждение справедливо в том случае, если все данные числа делятся на одно из них (доказательство приведено в следующем пункте этой статьи). Например, НОД(15, 60, −45)=15 . Это действительно так, так как 15 делит и число 15 , и число 60 , и число −45 , и не существует общего делителя чисел 15 , 60 и −45 , который превосходит 15 .

Особый интерес представляют так называемые взаимно простые числа , - такие целые числа, наибольший общий делитель которых равен единице.

Свойства наибольшего общего делителя, алгоритм Евклида

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

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

Наибольший общий делитель чисел a и b равен наибольшему общему делителю чисел b и a , то есть, НОД(a, b)=НОД(a, b) .

Это свойство НОД напрямую следует из определения наибольшего общего делителя.

Если a делится на b , то множество общих делителей чисел a и b совпадает со множеством делителей числа b , в частности, НОД(a, b)=b .

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

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

В частности, если числа a и b равны, то НОД(a, b)=НОД(a, a)=НОД(b, b)=a=b . К примеру, НОД(132, 132)=132 .

Доказанное свойство наибольшего делителя позволяет нам находить НОД двух чисел, когда одно из них делится на другое. При этом НОД равен одному из этих чисел, на которое делится другое число. Например, НОД(8, 24)=8 , так как 24 кратно восьми.

Если a=b·q+c , где a , b , c и q – целые числа, то множество общих делителей чисел a и b совпадает со множеством общих делителей чисел b и c , в частности, НОД(a, b)=НОД(b, c) .

Обоснуем это свойство НОД.

Так как имеет место равенство a=b·q+c , то всякий общий делитель чисел a и b делит также и c (это следует из свойств делимости). По этой же причине, всякий общий делитель чисел b и c делит a . Поэтому совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и c . В частности, должны совпадать и наибольшие из этих общих делителей, то есть, должно быть справедливо следующее равенство НОД(a, b)=НОД(b, c) .

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

Прежде чем дать формулировку теоремы, рекомендуем освежить в памяти теорему из раздела теории , которая утверждает, что делимое a может быть представлено в виде b·q+r , где b – делитель, q – некоторое целое число, называемое неполным частным, а r – целое число, удовлетворяющее условию , называемое остатком.

Итак, пусть для двух ненулевых целых положительных чисел a и b справедлив ряд равенств

заканчивающийся, когда r k+1 =0 (что неизбежно, так как b>r 1 >r 2 >r 3 , … - ряд убывающих целых чисел, и этот ряд не может содержать более чем конечное число положительных чисел), тогда r k – это наибольший общий делитель чисел a и b , то есть, r k =НОД(a, b) .

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

Докажем сначала, что r k является общим делителем чисел a и b , после чего покажем, что r k не просто делитель, а наибольший общий делитель чисел a и b .

Будем двигаться по записанным равенствам снизу вверх. Из последнего равенства можно сказать, что r k−1 делится на r k . Учитывая этот факт, а также предыдущее свойство НОД, предпоследнее равенство r k−2 =r k−1 ·q k +r k позволяет утверждать, что r k−2 делится на r k , так как и r k−1 делится на r k и r k делится на r k . По аналогии из третьего снизу равенства заключаем, что r k−3 делится на r k . И так далее. Из второго равенства получаем, что b делится на r k , а из первого равенства получаем, что a делится на r k . Следовательно, r k является общим делителем чисел a и b .

Осталось доказать, что r k =НОД(a, b) . Для достаточно показать, что любой общий делитель чисел a и b (обозначим его r 0 ) делит r k .

Будем двигаться по исходным равенствам сверху вниз. В силу предыдущего свойства из первого равенства следует, что r 1 делится на r 0 . Тогда из второго равенства получаем, что r 2 делится на r 0 . И так далее. Из последнего равенства получаем, что r k делится на r 0 . Таким образом, r k =НОД(a, b) .

Из рассмотренного свойства наибольшего общего делителя следует, что множество общих делителей чисел a и b совпадает с множеством делителей наибольшего общего делителя этих чисел. Это следствие из алгоритма Евклида позволяет найти все общие делители двух чисел как делители НОД этих чисел.

Пусть a и b – целые числа, одновременно не равные нулю, тогда существуют такие целые числа u 0 и v 0 , то справедливо равенство НОД(a, b)=a·u 0 +b·v 0 . Последнее равенство представляет собой линейное представление наибольшего общего делителя чисел a и b , это равенство называют соотношением Безу, а числа u 0 и v 0 – коэффициентами Безу.

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

По алгоритму Евклида мы можем записать следующие равенства

Из первого равенства имеем r 1 =a−b·q 1 , и, обозначив 1=s 1 и −q 1 =t 1 , это равенство примет вид r 1 =s 1 ·a+t 1 ·b , причем числа s 1 и t 1 - целые. Тогда из второго равенства получим r 2 =b−r 1 ·q 2 = b−(s 1 ·a+t 1 ·b)·q 2 =−s 1 ·q 2 ·a+(1−t 1 ·q 2)·b . Обозначив −s 1 ·q 2 =s 2 и 1−t 1 ·q 2 =t 2 , последнее равенство можно записать в виде r 2 =s 2 ·a+t 2 ·b , причем s 2 и t 2 – целые числа (так как сумма, разность и произведение целых чисел является целым числом). Аналогично из третьего равенства получим r 3 =s 3 ·a+t 3 ·b , из четвертого r 4 =s 4 ·a+t 4 ·b , и так далее. Наконец, r k =s k ·a+t k ·b , где s k и t k - целые. Так как r k =НОД(a, b) , и, обозначив s k =u 0 и t k =v 0 , получим линейное представление НОД требуемого вида: НОД(a, b)=a·u 0 +b·v 0 .

Если m – любое натуральное число, то НОД(m·a, m·b)=m·НОД(a, b) .

Обоснование этого свойства наибольшего общего делителя таково. Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД(m·a, m·b)=m·r k , а r k – это НОД(a, b) . Следовательно, НОД(m·a, m·b)=m·НОД(a, b) .

На этом свойстве наибольшего общего делителя основан способ нахождения НОД с помощью разложения на простые множители .

Пусть p – любой общий делитель чисел a и b , тогда НОД(a:p, b:p)=НОД(a, b):p , в частности, если p=НОД(a, b) имеем НОД(a:НОД(a, b), b:НОД(a, b))=1 , то есть, числа a:НОД(a, b) и b:НОД(a, b) - взаимно простые.

Так как a=p·(a:p) и b=p·(b:p) , и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД(a, b)=НОД(p·(a:p), p·(b:p))= p·НОД(a:p, b:p) , откуда и следует доказываемое равенство.

Только что доказанное свойство наибольшего общего делителя лежит в основе .

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

Наибольший общий делитель чисел a 1 , a 2 , …, a k равен числу d k , которое находится при последовательном вычислении НОД(a 1 , a 2)=d 2 , НОД(d 2 , a 3)=d 3 , НОД(d 3 , a 4)=d 4 , …, НОД(d k-1 , a k)=d k .

Доказательство базируется на следствии из алгоритма Евклида. Общие делители чисел a 1 и a 2 совпадают с делителями d 2 . Тогда общие делители чисел a 1 , a 2 и a 3 совпадают с общими делителями чисел d 2 и a 3 , следовательно, совпадают с делителями d 3 . Общие делители чисел a 1 , a 2 , a 3 и a 4 совпадают с общими делителями d 3 и a 4 , следовательно, совпадают с делителями d 4 . И так далее. Наконец, общие делители чисел a 1 , a 2 , …, a k совпадают с делителями d k . А так как наибольшим делителем числа d k является само число d k , то НОД(a 1 , a 2 , …, a k)=d k .

На этом закончим обзор основных свойств наибольшего общего делителя.

Список литературы.

Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
Виноградов И.М. Основы теории чисел.
Михелович Ш.Х. Теория чисел.
Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.

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

Калькулятор для нахождения НОД и НОК

Найти НОД и НОК

Найдено НОД и НОК: 5806

Как пользоваться калькулятором

Введите числа в поле для ввода
В случае ввода некорректных символов поле для ввода будет подсвечено красным
нажмите кнопку "Найти НОД и НОК"

Как вводить числа

Числа вводятся через пробел, точку или запятую
Длина вводимых чисел не ограничена , так что найти НОД и НОК длинных чисел не составит никакого труда

Что такое НОД и НОК?

Наибольший общий делитель нескольких чисел – это наибольшее натуральное целое число, на которое все исходные числа делятся без остатка. Наибольший общий делитель сокращённо записывается как НОД .
Наименьшее общее кратное нескольких чисел – это наименьшее число, которое делится на каждое из исходных чисел без остатка. Наименьшее общее кратное сокращённо записывается как НОК .

Как проверить, что число делится на другое число без остатка?

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

Некоторые признаки делимости чисел

1. Признак делимости числа на 2
Чтобы определить, делится ли число на два (является ли оно чётным), достаточно посмотреть на последнююю цифру этого числа: если она равна 0, 2, 4, 6 или 8, то число чётно, а значит делится на 2.
Пример: определить, делится ли на 2 число 34938 .
Решение: смотрим на последнюю цифру: 8 - значит число делится на два.

2. Признак делимости числа на 3
Число делится на 3 тогда, когда сумма его цифр делится на три. Таким образом, чтобы определить, делится ли число на 3, нужно посчитать сумму цифр и проверить, делится ли она на 3. Даже если сумма цифр получилась очень большой, можно повторить этот же процесс вновь.
Пример: определить, делится ли число 34938 на 3.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 3, а значит и число делится на три.

3. Признак делимости числа на 5
Число делится на 5 тогда, когда его последняя цифра равна нулю или пяти.
Пример: определить, делится ли число 34938 на 5.
Решение: смотрим на последнюю цифру: 8 - значит число НЕ делится на пять.

4. Признак делимости числа на 9
Этот признак очень похож на признак делимости на тройку: число делится на 9 тогда, когда сумма его цифр делится на 9.
Пример: определить, делится ли число 34938 на 9.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 9, а значит и число делится на девять.

Как найти НОД и НОК двух чисел

Как найти НОД двух чисел

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

Рассмотрим этот способ на примере нахождения НОД(28, 36) :

Раскладываем оба числа на множители: 28 = 1·2·2·7 , 36 = 1·2·2·3·3
Находим общие множители, то есть те, которые есть у обоих чисел: 1, 2 и 2.
Вычисляем произведение этих множителей: 1·2·2 = 4 - это и есть наибольший общий делитель чисел 28 и 36.

Как найти НОК двух чисел

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

Для вычисления НОК нужно вычислить произведение исходных чисел и затем разделить его на предварительно найденный НОД. Найдём НОК для тех же чисел 28 и 36:

Находим произведение чисел 28 и 36: 28·36 = 1008
НОД(28, 36), как уже известно, равен 4
НОК(28, 36) = 1008 / 4 = 252 .

Нахождение НОД и НОК для нескольких чисел

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

Аналогичное соотношение действует и для наименьшего общего кратного чисел: НОК(a, b, c) = НОК(НОК(a, b), c)

Пример: найти НОД и НОК для чисел 12, 32 и 36.

Cперва разложим числа на множители: 12 = 1·2·2·3 , 32 = 1·2·2·2·2·2 , 36 = 1·2·2·3·3 .
Найдём обшие множители: 1, 2 и 2 .
Их произведение даст НОД: 1·2·2 = 4
Найдём теперь НОК: для этого найдём сначала НОК(12, 32): 12·32 / 4 = 96 .
Чтобы найти НОК всех трёх чисел, нужно найти НОД(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , НОД = 1·2·2·3 = 12 .
НОК(12, 32, 36) = 96·36 / 12 = 288 .

Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например :

Число 12 делится на 1, на 2, на 3, на 4, на 6, на 12;

Число 36 делится на 1, на 2, на 3, на 4, на 6, на 12, на 18, на 36.

Числа, на которые число делится нацело (для 12 это 1, 2, 3, 4, 6 и 12) называются делителями числа . Делитель натурального числа a - это такое натуральное число, которое делит данное число a без остатка. Натуральное число, которое имеет более двух делителей, называется составным . Обратите внимание, что числа 12 и 36 имеют общие делители. Это числа: 1, 2, 3, 4, 6, 12. Наибольший из делителей этих чисел - 12.

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

Кратко наибольший общий делитель чисел a и b записывают так:

Пример : НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример:

НОД (7; 9) = 1

Числа 7 и 9 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми чи слами .

Взаимно простые числа - это натуральные числа, которые имеют только один общий делитель - число 1. Их НОД равен 1.

Наибольший общий делитель (НОД), свойства.

Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример : для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
Следствие 1: множество общих делителей m и n совпадает с множеством делителей НОД(m , n ).
Следствие 2: множество общих кратных m и n совпадает с множеством кратных НОК (m , n ).

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

Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:

и поэтому представим в виде линейной комбинации чисел m и n :

Это соотношение называется соотношением Безу , а коэффициенты u и v — коэффициентами Безу . Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД (a 1 , a 2 , … , a n ).

Вычисление наибольшего общего делителя (НОД).

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм . Кроме того, значение НОД (m ,n ) можно легко вычислить, если известно каноническое разложение чисел m и n на простые множители:

где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД (m ,n ) и НОК (m ,n ) выражаются формулами:

Если чисел более двух: , их НОД находится по следующему алгоритму:

— это и есть искомый НОД.

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

Разберем пошагово вычисление наибольшего общего делителя:

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

Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое, справа - делитель. Далее в левом столбце записываем значения частных. Поясним сразу на примере. Разложим на простые множители числа 28 и 64.