Делимость, признаки делимости

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


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


Общие делители – определение, примеры

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

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

Дадим определение общего делителя нескольких целых чисел.

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

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

Приведем несколько примеров общих делителей. Целое число 3 – это общий делитель двух целых чисел 9 и −12, так как 3 является делителем и числа 9 (так как 9=3·3), и числа −12 (так как −12=3·(−4)). Другими общими делителями чисел 3 и −12 являются числа 1, −1 и −3. Рассмотрим еще один пример. Четыре целых числа 3, −11, −8 и 19 имеют общие делители 1 и −1.

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

Также нужно отметить, что если целое число b - общий делитель нескольких целых чисел, то противоположное число −b также есть общий делитель данных чисел.

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

Наибольший общий делитель (НОД) – определение, обозначение и примеры


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

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

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

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

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

Для краткой записи наибольшего общего делителя часто используют аббревиатуру НОД – Наибольший Общий Делитель. Также наибольший общий делитель двух чисел 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 целых чисел a1, a2, …, an мы будем обозначать как НОД(a1, a2, …, an). Если найдено значение b наибольшего общего делителя этих чисел, то можно записать НОД(a1, a2, …, an)=b.

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

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

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

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

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

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

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

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

  2. Если 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 кратно восьми.

  3. Если 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

    Из первого равенства имеем r1=a−b·q1, и, обозначив 1=s1 и −q1=t1, это равенство примет вид r1=s1·a+t1·b, причем числа s1 и t1 - целые. Тогда из второго равенства получим r2=b−r1·q2=b−(s1·a+t1·b)·q2=−s1·q2·a+(1−t1·q2)·b. Обозначив −s1·q2=s2 и 1−t1·q2=t2, последнее равенство можно записать в виде r2=s2·a+t2·b, причем s2 и t2 – целые числа (так как сумма, разность и произведение целых чисел является целым числом). Аналогично из третьего равенства получим r3=s3·a+t3·b, из четвертого r4=s4·a+t4·b, и так далее. Наконец, rk=sk·a+tk·b, где sk и tk - целые. Так как rk=НОД(a, b), и, обозначив sk=u0 и tk=v0, получим линейное представление НОД требуемого вида: НОД(a, b)=a·u0+b·v0.

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

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

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

  7. Пусть 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), откуда и следует доказываемое равенство.

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

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

    Наибольший общий делитель чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3, НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.

    Доказательство базируется на следствии из алгоритма Евклида. Общие делители чисел a1 и a2 совпадают с делителями d2. Тогда общие делители чисел a1, a2 и a3 совпадают с общими делителями чисел d2 и a3, следовательно, совпадают с делителями d3. Общие делители чисел a1, a2, a3 и a4 совпадают с общими делителями d3 и a4, следовательно, совпадают с делителями d4. И так далее. Наконец, общие делители чисел a1, a2, …, ak совпадают с делителями dk. А так как наибольшим делителем числа dk является само число dk, то НОД(a1, a2, …, ak)=dk.

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

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

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