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

Теория делимости.

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

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

Как бы то ни было, человечеством была освоена главная идея, лежащая в основе понятия о натуральном числе. Идея взаимно-однозначного соответствия или биекции между элементами разных множеств.

Множество натуральных чисел сейчас принято обозначать ажурной заглавной буквой N.Натуральными числами являются {1,2,3,…}. Понятие о нуле возникло гораздо позже, чем об остальных целых числах. Ноль обозначает ничто, однако 0 – вполне осязаемый символ ничем не хуже чем 1 или 5. Ноль – это нечто, а обозначает он ничто. Нечто обозначающее ничто – это уже шаг к раздвоению личности и он нормальным людям дался нелегко. Отрицательные числа (понимаемые как долг, как недостача) вошли в сознание людей гораздо проще, так же как и дроби, понимаемые как часть единого целого.

Основные понятия и теоремы.

Предмет теории чисел – целые числа и их свойства.

Множество целых чисел обозначается символом Z, символом Z₊ обозначается множество целых положительных чисел, символом N– множество натуральных чисел. Латинскими малыми буквами здесь и далее будем обозначать целые числа.

Заметим, что

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

Если , (b≠0) , Тогда говорят, что а делится на b, или b делит а, и пишут b\a. Тогда а называем кратным числа b, а b – делителем числа а.

Справедливы следующие

Теоремы:

(1) m\a, b\m b\a.

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

m\a a=ma₁;

b\m m=bm₁ a=bm₁a₁. Обозначив b₁=a₁m₁, получим a=bb₁, причем b\a.

□

(2) Если в равенстве вида k+l+…+n=p+q+…+s относительно всех членов кроме одного известно, что они кратны b, то и один оставшийся член тоже кратен b.

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

Не нарушая общности, предположим, что таким членом (относительно кратности которого числу b ничего не известно) является k.

Тогда l₁, …, n₁, p₁, q₁, …, s₁: l=bl₁,…, n=bn₁, p=bp₁, q=bq₁, …, s=bs₁.

Тогда k=p+q+…+s–l–…–n=bp₁+bq₁+…+bs₁–bl₁–…–bn₁=b(p₁+q₁+…+s₁–l₁–…–n₁)

Обозначим k₁= p₁+q₁+…+s₁–l₁–…–n₁. Очевидно, k₁ – целое число, причем k=bk₁ Тогда, по определению делимости, b\k.

□

Кроме того, очевидны следующие свойства:

1) a\0, 1\a, a\a.

2) a\b, b\a a=±b.

3) a\b, a\c a\(bx+cy).

(Доказательство св-ва 3: b=ab₁, c=ac₁ bx+cy=ab₁x+ac₁y=a(b₁x+c₁y))

Теорема деления (теорема о делении с остатком)

единственная пара чисел 0 ≤ r < b: a=bq+r *

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

Возьмем q: bq≤a, b(q+1)>a. Такое целое q, очевидно, существует r=a–bq является целым положительным числом как разность двух целых чисел, первое из которых больше второго. Причем выполняется . Построением такого r доказано существование разложения (*).

Теперь докажем единственность разложения (*): предположим, что кроме построенного выше, имеется еще одно разложение числа a:

a=bq₁+r₁, 0≤r₁<b.

Вычтем полученное равенство из равенства (*) почленно. Получим

0=b(q–q₁)+(r–r₁). **

Поскольку b\0, b\b(q–q₁), то по теореме 2, b\(r–r₁).

С другой стороны, 0≤r<b, 0≤r₁<b |r–r₁|<b. Отсюда и из того, что b\(r–r₁), следует, что r–r₁=0, и тогда r=r₁. Подставляя полученное равенство в (**), получаем 0=b(q–q₁).

Но по условию теоремы, b≠0 , тогда q–q₁=0 q=q₁.

Таким образом, оба построенных разложения числа a совпадают, а значит разложение (*) единственно.

□

В разложении (*) число q называются неполным частным, r – остатком от деления a на b.

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

Далее будем рассматривать лишь положительные делители чисел.

Общим делителем чисел a₁, a₂,…,a_n называется число d: d\a_i .

Наибольший из всех общих делителей чисел a₁, a₂,…,a_n называется их наибольшим общим делителем (НОД) и обозначается НОД(a₁, a₂,…,a_n) или (a₁, a₂,…,a_n).

Если (a₁, a₂,…,a_n)=1, то числа a₁, a₂,…,a_n называются взаимно простыми.

Если (a_i,a_j)=1 , i≠j , то числа a₁, a₂,…,a_n называются попарно простыми.

Утверждение

Если числа a₁, a₂,…,a_n – попарно простые, то они взаимно простые. (Очевидно.)

Теорема 1

Если b\a совокупность общих делителей a и b совпадает с совокупностью делителей b. В частности, (a,b)=b.

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

b\a a=ba₁, тогда d: d\b справедливо d\a (т.е. любой делитель b является также делителем a).

Если l\a, но l не делит b, то l не является общим делителем a и b.

То есть совокупность общих делителей a и b совпадает с совокупностью делителей b. А поскольку наибольший делитель b есть b, и b\a , то (a,b)=b.

□

Теорема 2

Если a=bq+c, то совокупность общих делителей a и b совпадает с совокупностью общих делителей b и c.

В частности, (a,b)=(b,c)

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

Пусть m\a, m\b m\c (в силу a=bq+c и теоремы 2 п.1), а значит m – общий делитель b и c.

Пусть l\b, l\c l\a (в силу a=bq+c и теоремы 2 п.1), а значит l - общий делитель a и b.

Получили совпадение совокупности общих делителей a и b и общих делителей b и c.

Пусть теперь d=(a,b) d\a, d\b, а значит, по доказанному выше, d\c. В силу совпадения совокупностей общих делителей и того, что d – наименьший изо всех делителей a и b, не может существовать d₁: d₁>d, d₁\b, d₁\c. Поэтому d=(b,c) (a,b)= (b,c).

□

Алгоритм Евклида (отыскания НОД 2-х чисел)

Пусть a>b. Тогда в силу теоремы делимости находим ряд равенств:

a=bq₁+r₁, 0<r₁<b

b=r₁q₂+r₂, 0<r₂<r₁

r₁=r₂q₃+r₃, 0<r₃<r₂

...…………………

r_n-2=r_n-1q_n+r_n, 0<r_n<r_n-1

r_n_–₁=r_nq_n₊₁.

Получение последнего равенства (то есть равенства с разложением без остатка) неизбежно, т.к. ряд b, r₁, r₂, …. – ряд убывающих целых чисел, который не может содержать более b положительных чисел, а значит рано или поздно в этом ряду возникнет «0».

Видим, что общие делители a и b, b и r₁, r₁ и r₂,..., r_n_–1 и r_n совпадают с делителями числа r_n (a,b)=(b,r₁)=(r₁,r₂)=…=(r_n_-₁,r_n)= r_n.

Таким образом, (a,b)=r_n.

Вышеизложенная идея нахождения НОД может быть реализована в виде алгоритма. Ниже приведены несколько вариантов реализации алгоритма Евклида.

Реализация алгоритма Евклида (вариант алгоритма с вычитанием)

Вход: a, b>0.

1.Если a>b Шаг 3

если a<b Шаг 2

если a=b Шаг 5 (выход)

2.Меняем местами a и b.

3.a:=a–b

4.Возвращаемся на Шаг 1.

5. Выход: a – НОД

Ниже приведен пример использования этой реализации алгоритма.

Пример

a=603, b=108

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

Ответ: НОД(603,108)=9.

Реализация алгоритма Евклида (вариант алгоритма с делением с остатком)

Вход: a, b >0.

1. Находим разложение a=bq+r, 0≤r<b

2. если r=0 Шаг 5 (выход)

3. a:=b; b:=r.

4. Возвращаемся на Шаг 1

5. Выход: b – НОД.

Пример

a=603, b=108

a
b

603=5·108+63

108=1·63+45

63=1∙45+27

45=1∙27+18

27=1∙18+9

18=2∙9+0

Ответ: НОД(603,108)=9.

Бинарный алгоритм Евклида

Этот вариант создан специально для реализации на ЭВМ. В нем учитывается, что операция деления на число 2 или на любую степень двойки является весьма быстрой и простой операцией (в двоичной системе счисления операция деления на 2 есть всего лишь битовый сдвиг вправо).

Учтем, что (2^k∙a,2^s∙b)=2^min(k,s)(a,b).

Алгоритм:

Вход: a, b>0.

1. Представим a и b в виде: ; , где a₁, b₁ – нечетные числа.