Сейчас и в дальнейшем мы будем подразумевать, что хотя бы одно из данных чисел отлично от нуля. Если все данные числа равны нулю, то их общим делителем является любое целое число, а так как целых чисел бесконечно много, то мы не можем говорить о наибольшем из них. Следовательно, нельзя говорить о наибольшем общем делителе чисел, каждое из которых равно нулю.
Теперь мы можем дать определение наибольшего общего делителя двух чисел.
Определение.
Наибольший общий делитель двух целых чисел – это наибольшее целое число, делящее два данных целых числа.
Для краткой записи наибольшего общего делителя часто используют аббревиатуру НОД – Наибольший Общий Делитель. Также наибольший общий делитель двух чисел 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 класс: учебник для общеобразовательных учреждений.
- Виноградов И.М. Основы теории чисел.
- Михелович Ш.Х. Теория чисел.
- Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.
2 |
5 |
||||||
2 |
5 |
||||||
3 |
3 |
||||||
5 |
|||||||
60=2*2*3*5
75=3*5*5
2) Выпишем множители, входящие в разложение первого из этих чисел и добавим к ним недостающий множитель 5 из разложения второго числа. Получаем: 2*2*3*5*5=300. Нашли НОК, т.е. эта сумма = 300. Не забываем размерность и пишем ответ:
Ответ: Мама дает по 300 рублей.
Определение НОД: Наибольшим общим делителем (НОД) натуральных чисел а и в называют наибольшее натуральное число c , на которое и a , и b делятся без остатка. Т.е. c это нибольшее натуральное число, для которого и а и б являются кратными.
Памятка: Существуют два подхода к определению натуральных чисел
- числа, используемые при: перечислении (нумеровании) предметов (первый, второй, третий, …); - в школах, обычно так .
- обозначении количества предметов (нет покемонов - ноль, один покемон, два покемона, …).
Отрицательные и нецелые (рациональные, вещественные, …) числа натуральными не являются. Ноль некоторые авторы включают в множество натуральных чисел, другие - нет. Множество всех натуральных чисел принято обозначать символом N
Памятка:
Делителем натурального числа a
называют число b,
на которое a
делится без остатка. Кратным натуральному числу b
называют натуральное число a
, которое делится на b
без остатка. Если число b
- делитель числа a
, то a
кратно числу b
. Пример: 2 - делитель 4, а 4 кратно двум. 3 - делитель 12, а 12 кратно 3.
Памятка:
Натуральные числа называют простыми, если они делятся без остатка только на себя и на 1. Взаимно простыми называются числа у которых только один общий делитель, равный 1.
Определение как найти НОД в общем случае:
Чтобы найти НОД (Наибольший общий делитель)
нескольких натуральных чисел надо:
1) Разложить их на простые множители. (Для этого Вам может очень пригодиться Таблица простых чисел.)
2) Выписать множители, входящие в разложение одного из них.
3) Вычеркнуть те, которые не входят в разложение остальных чисел.
4) Перемножить множители, получившиеся в п.3).
Задача 2 на (НОК): К новому году Коля Пузатов купил в городе 48 хомяков и 36 кофейников. Фекла Дормидонтова, как самая честная девочка класса, получила задание разделить это имущество на наибольшее возможное число подарочных наборов для учителей. Какое число наборов получилось? Какой состав наборов?
Пример 2.1. решения задачи на нахождение НОД. Нахождение НОД подбором.
Решение:
Каждое из чисел и 48, и 36 должно делиться на число подарков.
1) Выпишем делители 48: 48, 24, 16, 12
, 8, 6, 3, 2, 1
2) Выпишем делители 36: 36, 18, 12
, 9, 6, 3, 2, 1 Выбираем наибольший общий делитель. Оп-ля-ля! Нашли, это число наборов 12 штук.
3) Поделим 48 на 12 получим 4, поделим 36 на 12, получим 3. Не забываем размерность и пишем ответ:
Ответ: Получится 12 наборов по 4 хомяка и 3 кофейника в каждом наборе.
Определение. Наибольшее натуральное число, на которое делятся без остатка числа а и b, называют наибольшим общим делителем (НОД) этих чисел.
Найдём наибольший общий делитель чисел 24 и 35.
Делителями 24 будут числа 1, 2, 3, 4, 6, 8, 12, 24, а делителями 35 будут числа 1, 5, 7, 35.
Видим, что числа 24 и 35 имеют только один общий делитель - число 1. Такие числа называют взаимно простыми
.
Определение. Натуральные числа называют взаимно простыми , если их наибольший общий делитель (НОД) равен 1.
Наибольший общий делитель (НОД) можно найти, не выписывая всех делителей данных чисел.
Разложим на множители числа 48 и 36, получим:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Из множителей, входящих в разложение первого из этих чисел, вычеркнем те, которые не входят в разложение второго числа
(т. е. две двойки).
Остаются множители 2 * 2 * 3. Их произведение равно 12. Это число и является наибольшим общим делителем чисел 48 и 36.
Так же находят наибольший общий делитель трёх и более чисел.
Чтобы найти наибольший общий делитель
2) из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел;
3) найти произ ведение оставшихся множителей.
Если все данные числа делятся на одно из них, то это число и является наибольшим общим делителем
данных чисел.
Например, наибольшим общим делителем чисел 15, 45, 75 и 180 будет число 15, так как на него делятся все остальные числа: 45, 75 и 180.
Наименьшее общее кратное (НОК)
Определение.
Наименьшим общим кратным (НОК)
натуральных чисел а и Ь называют наименьшее натуральное число,
которое кратно и a, и b.
Наименьшее общее кратное (НОК) чисел 75 и 60 можно найти и не выписывая подряд кратные этих чисел. Для этого разложим 75 и 60 на
простые множители: 75 = 3 * 5 * 5, а 60 = 2 * 2 * 3 * 5.
Выпишем множители, входящие в разложение первого из этих чисел, и добавим к ним недостающие множители 2 и 2 из разложения
второго числа (т.е. объединяем множители).
Получаем пять множителей 2 * 2 * 3 * 5 * 5, произведение которых равно 300. Это число является наименьшим общим кратным чисел 75 и 60.
Так же находят наименьшее общее кратное для трёх и более чисел.
Чтобы найти наименьшее общее кратное
нескольких натуральных чисел, надо:
1) разложить их на простые множители;
2) выписать множители, входящие в разложение одного из чисел;
3) добавить к ним недостающие множители из разложений остальных чисел;
4) найти произведение получившихся множителей.
Заметим, что если одно из данных чисел делится на все остальные числа, то это число и является наименьшим общим кратным данных
чисел.
Например, наименьшим общим кратным чисел 12, 15, 20 и 60 будет число 60, так как оно делится на все данные числа.
Пифагор (VI в. до н. э.) и его ученики изучали вопрос о делимости чисел. Число, равное сумме всех его делителей (без самого числа),
они называли совершенным числом. Например, числа 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) совершенные. Следующие совершенные
числа - 496, 8128, 33 550 336. Пифагорейцы знали только первые три совершенных числа. Четвёртое - 8128 - стало известно в I в. н. э.
Пятое - 33 550 336 - было найдено в XV в. К 1983 г. было известно уже 27 совершенных чисел. Но до сих пор учёные не знают, есть ли
нечётные совершенные числа, есть ли самое большое совершенное число.
Интерес древних математиков к простым числам связан с тем, что любое число либо простое, либо может быть представлено в виде
произведения простых чисел, т. е. простые числа - это как бы кирпичики, из которых строятся остальные натуральные числа.
Вы, наверное, обратили внимание, что простые числа в ряду натуральных чисел встречаются неравномерно - в одних частях ряда их больше,
в других - меньше. Но чем дальше мы продвигаемся по числовому ряду, тем реже встречаются простые числа. Возникает вопрос: существует
ли последнее (самое большое) простое число? Древнегреческий математик Евклид (III в. до н. э.) в своей книге «начала», бывшей на
протяжении двух тысяч лет основным учебником математики, доказал, что простых чисел бесконечно много, т. е. за каждым простым числом
есть ещё большее простое число.
Для отыскания простых чисел другой греческий математик того же времени Эратосфен придумал такой способ. Он записывал все числа
от 1 до какого-то числа, а потом вычёркивал единицу, которая не является ни простым, ни составным числом, затем вычёркивал через
одно все числа, идущие после 2 (числа, кратные 2, т. е. 4, 6, 8 и т. д.). Первым оставшимся числом после 2 было 3. Далее
вычёркивались через два все числа, идущие после 3 (числа, кратные 3, т. е. 6, 9, 12 и т. д.). в конце концов оставались
невычеркнутыми только простые числа.
Чтобы научиться находить наибольший общий делитель двух или нескольких чисел, необходимо разобраться с тем, что представляют из себя натуральные, простые и сложные числа.
Натуральным называется любое число, которое используется при подсчете целых предметов.
Если натуральное число можно разделить только на само себя и единицу, то его называют простым.
Все натуральные числа можно разделить на себя и единицу, однако единственным четным простым числом является 2, все остальные можно поделить на двойку. Поэтому простыми могут быть только нечетные числа.
Простых чисел достаточно много, полного списка их не существует. Для нахождения НОД удобно использовать специальные таблицы с такими числами.
Большинство натуральных чисел могут делиться не только на единицу, самих себя, но и на другие числа. Так, например, число 15 можно поделить еще на 3 и 5. Все их называют делителями числа 15.
Таким образом, делитель любого А - это число, на которое оно может быть разделено без остатка. Если у числа имеется более двух натуральных делителей, его называют составным.
У числа 30 можно выделить такие делители, как 1, 3, 5, 6, 15, 30.
Можно заметить, что 15 и 30 имеют одинаковые делители 1, 3, 5, 15. Наибольший общий делитель этих двух чисел - 15.
Таким образом, общим делителем чисел А и Б называется такое число, на которое можно поделить их нацело. Наибольшим можно считать максимальное общее число, на которое можно их разделить.
Для решения задач используется такая сокращенная надпись:
НОД (А; Б).
Например, НОД (15; 30) = 30.
Чтобы записать все делители натурального числа, применяется запись:
Д (15) = {1, 3, 5, 15}
НОД (9; 15) = 1
В данном примере у натуральных чисел имеется только один общий делитель. Их называют взаимно простыми, соответственно единица и является их наибольшим общим делителем.
Как найти наибольший общий делитель чисел
Чтобы найти НОД нескольких чисел, нужно:
Найти все делители каждого натурального числа по отдельности, то есть разложить их на множители (простые числа);
Выделить все одинаковые множители у данных чисел;
Перемножить их между собой.
Например, чтобы вычислить наибольший общий делитель чисел 30 и 56, нужно записать следующее:
Чтобы не путаться при , удобно записывать множители при помощи вертикальных столбиков. В левой части от черты нужно разместить делимое, а в правой - делитель. Под делимым следует указать получившееся частное.
Так, в правом столбце окажутся все нужные для решения множители.
Одинаковые делители (найденные множители) можно для удобства подчеркнуть. Их следует переписать и перемножить и записать наибольший общий делитель.
НОД (30; 56) = 2 * 5 = 10
Вот так просто на самом деле найти наибольший общий делитель чисел. Если немного потренироваться, делать это можно будет практически на автомате.
Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел 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 .
Давайте разберемся, как выглядит процесс нахождения НОД нескольких чисел, рассмотрев решение примера.
Пример.
Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .
Решение.
В этом примере a 1 =78 , a 2 =294 , a 3 =570 , a 4 =36 .
Сначала по алгоритму Евклида определим наибольший общий делитель d 2 двух первых чисел 78 и 294 . При делении получаем равенства 294=78·3+60 ; 78=60·1+18 ;60=18·3+6 и 18=6·3 . Таким образом, d 2 =НОД(78, 294)=6 .
Теперь вычислим d 3 =НОД(d 2 , a 3)=НОД(6, 570) . Опять применим алгоритм Евклида:570=6·95 , следовательно, d 3 =НОД(6, 570)=6 .
Осталось вычислить d 4 =НОД(d 3 , a 4)=НОД(6, 36) . Так как 36 делится на 6 , тоd 4 =НОД(6, 36)=6 .
Таким образом, наибольший общий делитель четырех данных чисел равен d 4 =6 , то есть,НОД(78, 294, 570, 36)=6 .
Ответ:
НОД(78, 294, 570, 36)=6 .
Разложение чисел на простые множители также позволяет вычислять НОД трех и большего количества чисел. В этом случае наибольший общий делитель находится как произведение всех общих простых множителей данных чисел.
Пример.
Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.
Решение.
Разложим числа 78 , 294 , 570 и 36 на простые множители, получаем 78=2·3·13 ,294=2·3·7·7 , 570=2·3·5·19 , 36=2·2·3·3 . Общими простыми множителями всех данных четырех чисел являются числа 2 и 3 . Следовательно, НОД(78, 294, 570, 36)=2·3=6 .
Ответ:
НОД(78, 294, 570, 36)=6 .
К началу страницы
Нахождение НОД отрицательных чисел
Если одно, несколько или все числа, наибольший делитель которых нужно найти, являются отрицательными числами, то их НОД равен наибольшему общему делителю модулей этих чисел. Это связано с тем, что противоположные числа a и −a имеют одинаковые делители, о чем мы говорили при изучении свойств делимости.
Пример.
Найдите НОД отрицательных целых чисел −231 и −140 .
Решение.
Модуль числа −231 равен 231 , а модуль числа −140 равен 140 , иНОД(−231, −140)=НОД(231, 140) . Алгоритм Евклида дает нам следующие равенства:231=140·1+91 ; 140=91·1+49 ; 91=49·1+42 ; 49=42·1+7 и 42=7·6 . Следовательно,НОД(231, 140)=7 . Тогда искомый наибольший общий делитель отрицательных чисел−231 и −140 равен 7 .
Ответ:
НОД(−231, −140)=7 .
Пример.
Определите НОД трех чисел −585 , 81 и −189 .
Решение.
При нахождении наибольшего общего делителя отрицательные числа можно заменить их абсолютными величинами, то есть, НОД(−585, 81, −189)=НОД(585, 81, 189) . Разложения чисел 585 , 81 и 189 на простые множители имеют соответственно вид585=3·3·5·13 , 81=3·3·3·3 и 189=3·3·3·7 . Общими простыми множителями этих трех чисел являются 3 и 3 . Тогда НОД(585, 81, 189)=3·3=9 , следовательно,НОД(−585, 81, −189)=9 .
Ответ:
НОД(−585, 81, −189)=9 .
35. Корені многочлена. Теорема Безу. (33 и выше)
36. Кратні корені, критерій кратності кореня.
