Наибольший общий делитель. Лирическое отступление - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Наибольший общий делитель. Нахождение наибольшего общего делителя... 1 17.91kb.
Программа по математике I. Основные понятия 1 44.47kb.
Отчет по практике.: Маленькое лирическое отступление. Владельцем... 1 25.58kb.
Если числитель и знаменатель дроби умножить или разделить на одно... 1 16.97kb.
Счетчик делитель на 8 с дешифратором 1 64.52kb.
За чистоту родного края 1 144.37kb.
«Мир друзей в стихотворениях Валентина Берестова» 1 58.31kb.
Тест по математике в 5 классе 1 вариант 1 61.71kb.
Делитель ручной И8-хрд. Украина 1 88.27kb.
Сентиментализм в творчестве Томаса Грея 1 83.76kb.
Сто великих загадок XX века москва вече 52 7549.05kb.
Перечень вибрационного и сопутствующего технологического оборудования 1 65.18kb.
Направления изучения представлений о справедливости 1 202.17kb.

Наибольший общий делитель. Лирическое отступление - страница №1/1

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

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

Определение. Общим делителем двух целых чисел a и b (хотя бы одно из этих чисел не равно нулю) называется любое такое целое число c (не равное нулю, конечно), что a делится на c и b делится на c.

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

Замечание 1. Как мы уже могли убедиться, описать в определении можно все что угодно. Поэтому, чтобы не принять на веру, возможно, полный бред, для каждого определения нужно проверить корректность того, что определяется. В данном случае нам надо проверить то, что НОД существует и единственен (помните, то же самое надо было доказывать про целую часть вещественного числа). Итак,

Лемма. Для любых целых a, b, a2+b2<>0 (именно так математики любят записывать условие того, что хотя бы одно из этих чисел не равно нулю) их НОД существует и единственен.

Доказательство. Заметим, что так как любое число делится на 1, то множество общих делителей непусто (оно обязательно содержит эту самую единичку). С другой стороны, любой делитель числа по модулю не больше этого числа (см. свойства делимости). Поэтому множество всех делителей числа b конечно (все они целые и лежат в промежутке от -|b| до |b|), то же самое можно сказать и про делители числа a. Поэтому и множество общих делителей этих двух чисел конечно (оно является пересечением множеств делителей чисел a и b, см. §0), а из конечного непустого множества всегда можно выбрать максимальный элемент, причем единственным образом (любимым методом прилежных кружковцев – полным перебором).

Замечание 2. Для " a, b целых, a2+b2<>0, НОД(a, b)>0.

Доказательство. Т. к. 1 – общий делитель a и b, то НОД(a, b) не меньше 1, и, значит, больше 0.

Замечание 3. Вообще-то, то определение НОД, которое мы ввели – довольно "школьное" и математики его не любят. Математикам больше нравится, когда НОД двух чисел определяют как такой общий их делитель, который делится на все остальные общие делители. Мы позже докажем равносильность этих двух определений, а пока отметим, что пользуясь вторым определением, легче доказать свойства НОД, но зато доказать корректность этого другого определения очень непросто.

Теорема (свойства НОД(a, b)). Для " a, b целых, a2+b2<>0, верно:

1. НОД(a, b) = НОД(b, a)



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

2. НОД(a, b) = НОД(|a|, |b|)

Докажите это сами.

3. НОД(a, b)=max(|a|, |b|).



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

3a. При a <> 0, b <> 0 НОД(a, b)=min(|a|, |b|)

4. НОД(a,0)=a.

Доказательство. Очевидно, что a – общий делитель чисел a и 0. Но к тому же и наибольший по св-ву 3.

5. НОД(a,1)=1.



Доказательство. 1 делится только на ±1. При этом по замечанию 2 НОД всегда положителен. Значит, он – единица.

6. Если u – целое, то НОД(a+bu, b) = НОД(a, b).



Доказательство. Пусть НОД(a, b) = d, НОД(a+bu,b)=e. Тогда a+bu делится на d, b делится на d Þ d – общий делитель a+bu и b Þ e=d. С другой стороны, (a+bu)-bu = a делится на e Þ e – общий делитель a и b Þ d=e. Таким образом, получаем, что, с одной стороны, e=d, с другой - d=e, значит, они равны.

Следствие 1 (очень важное!) – Алгоритм Евклида.

Рассмотрим пару целых чисел a и b, причем хоть одно из них не нуль, и будем искать их НОД следующим образом (ввиду свойства 2 достаточно рассмотреть случай неотрицательных чисел). Мы можем считать, что a=b (иначе просто поменяем a и b местами). Если оба числа – не нули (если хоть одно из них – ноль, то по св-ву 4 их НОД равен второму числу), то поделим a на b с остатком: a=bq0+r0. Если r0<>0, то поделим b с остатком на r0: b=r0q1+r1. Если r1<>0, то поделим r0 с остатком на r1: r0=r1q2+r2, и так далее. Тогда утверждается, что, во-первых, когда-нибудь этот процесс закончится , т. е. мы получим нулевой остаток после одного из делений с остатком: rn-1=rnqn+1+rn+1 , где rn+1=0, и, во-вторых, тогда НОД пары исходных чисел будет равен rn, т. е. последнему ненулевому остатку в последовательности r1, r2, r3, r4, …



Доказательство. (1) Докажем, что этот процесс конечен. В самом деле, b>r0>r1>r2>… (*) по определению деления с остатком (остаток меньше делителя). Предположим, что процесс бесконечен. Тогда все остатки в последовательности (*) ненулевые, значит, все они положительные. Но они к тому же натуральны, и, раз последовательность строго убывающая, различны, а натуральных чисел, меньших b, всего-то b штук, т. е. конечное число. Противоречие. Значит, какой-нибудь остаток (в наших обозначениях rn), будет равным нулю.

(2). Теперь докажем, что алгоритм Евклида действительно дает НОД. По свойству 6 НОД(a,b)=НОД(r0,b) (полагаем u:= -q0). Но аналогично (по все тому же св-ву 6) получаем НОД(r0,b)=НОД(r0,r1)=НОД(r2,r1)=…=НОД(r0,0)=r0. Но (гип-гип-ура!) и НОД(a,b)=r0.

7. (Теорема о линейном представлении НОД). Для " a, b целых, a2+b2<>0, $ x, y целые, такие что ax+by=НОД(a,b).

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

Доказательство. Как мы знаем, НОД(a,b) – последний ненулевой остаток в последовательности (*) (см. алгоритм Евклида), т. е. НОД(a,b) = rn (в наших обозначениях). Но rn-2 = rn-1qn + rn (см. выше), поэтому rn = rn-2rn-1qn. То есть мы выразили rn через rn-2 и rn-1. Аналогично rn-3 = rn-2qn-1 + rn-1 Þ

rn-1 = rn-3rn-2qn-1Þ rn= rn-2 – (rn-3rn-2qn-1)qn = Arn-2 + Brn-3, где A и B – какие-то целые числа, получающиеся после раскрытия скобок. Значит, мы выразили rn через rn-3 и rn-2. Будем теперь выражать rn-2 через rn-3 и rn-4, rn-3 через rn-4 и rn-5 и т. д. В результате когда-нибудь (за n-1 шаг, т. е. за конечное число шагов) мы выразим rn через r0 и r1: rn = A'r0 + B'r1, где A' и B' – какие-то целые числа. Но

b = r0q1 + r1 Þ r1 = r0q1b, a = bq0+r0 Þ r0 = bq0a Þ r0 и r1 можно выразить через a и b Þ r0 можно выразить через a и b все в том же виде rn = A''a + B''b, что и требовалось доказать (осталось положить x:=A'', y:=B'').

8. Для " сÎZ, с<>0, верно НОД(ca, cb) = |c|НОД(a,b).



Доказательство. Достаточно рассмотреть случай натурального c ( докажите это сами, основываясь на только что изученных свойствах НОД). При натуральном c нам надо д-ть, что НОД(ca, cb) = cНОД(a,b). Рассмотрим получение НОД(a,b) по алгоритму Евклида: a=bq0+r0, b=r0q1+r1 и т. д. до rn-1=rnqn+1 + rn+1, где rn+1=0. Если мы каждое из этих равенств домножим на c (ac=bcq0+cr0, bc=r0cq1+cr1,…) то все они сохранятся и ни одно из условий алгоритма Евклида не нарушится, т. е. ни один остаток не станет больше делителя (в самом деле, b>r0 Þ bc>сr0, r0>r1Þ сr0>сr1 и т. д.), а (n+1)-й остаток тоже будет равен 0 (rn+1=0 Þ crn+1=0) Þ последним ненулевым остатком будет crn . Значит, раз НОД(a,b) = rn, то crn = cНОД(a,b), но по алгоритму Евклида, примененному нами только что к числам ca и cb получаем, что НОД(ca, cb) = crn. Поэтому НОД(ca, cb) = cНОД(a,b).

Ну а теперь та самая теорема о равносильности двух определений НОД, о которой речь шла еще в замечании 3. Приготовились<>… Начали:



Теорема (о равносильности двух определений НОД(a, b)).

Для " a, b целых, a2+b2<>0, если d = НОД(a, b), e – общий делитель, больший нуля, такой что для " c – общего делителя a и b верно, что e делится на c, то e = d.



Доказательство. Докажем сначала, что если такие общие делители, как e (т. е. делящие все остальные общие делители), есть, то все они равны d (и, следовательно, их не больше, чем один). В самом деле, e делится на все общие делители a и b Þ e делится на d Þ (так как e и d положительны) e=d, но так как d – наибольший из всех общих делителей, d=e. Таким образом, если существует e – общий делитель a и b, больший нуля, такой что для " c – общего делителя a и b верно, что e делится на c, то e = d.

Теперь установим, что такое e действительно существует: докажем, что для " c – общего делителя a и b верно, что d делится на c. В самом деле, по св-ву 7 НОД (теореме о линейном разложении НОД) существуют x, y целые, такие что ax+by=d. Но раз c – общий делитель a и b, то ax делится на c, by тоже делится на cÞ ax+by делится на c Þ d делится на c. Теорема доказана.



Определение. Рассмотрим множество целых чисел a1, a2, a3, a4,…,an, хотя бы одно из которых не равно нулю. Тогда общим делителем этих чисел называется любое такое целое c (не нуль), что для " i=1,…,n ai делится на c.

Определение. Наибольший из всех общих делителей этих чисел называется их наибольшим общим делителем и обозначается НОД(a1, a2, a3, a4,…,an) или просто (a1, a2, a3, a4,…,an).

Замечание 4. Мы не будем рассматривать свойства НОД нескольких чисел в этом параграфе, хотя, возможно, это и стоило бы сделать именно здесь. Но мы вернемся к их рассмотрению несколько позже, когда будем говорить о НОК и НОД нескольких чисел.

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




Когда в Поднебесной много запретов, народ беднеет. Лао-цзы
ещё >>