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

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

Общим делителем чисел 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–1=r_nq_n+1.

Получение последнего равенства (то есть равенства с разложением без остатка) неизбежно, т.к. ряд 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-1,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	603	108	63	45	27	18
b	108	63	45	27	18	9

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₁ – нечетные числа.

k:=min(k₁,k₂).

2. Если a₁>b₁Шаг 4

a₁< b₁Шаг 3

a₁= b₁ Шаг 6

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

4. c:=a₁–b₁=2^s∙c₁ (c₁ - нечетное число)

(Заметим, что с обязательно будет четным, а значит )

5. a₁:= b₁ , b₁:=c₁ . Возвращаемся на Шаг 1.

6. Выход: (a,b)=2^k∙a₁ .

Пример

a=603, b=108

a1	603	27	9
b1	27	9	9
c1	9	9	–

1. a₁=603, k₁=0; b=108=4∙27=2²∙27 k₂=2, b₁=27, k=0

2. a₁=603> b₁=27 Ш4

4. c=603-27=56=64∙9, c₁=9

5. a₁=27; b₁=9 Ш1

1. a₁=27; b₁=9

2. a₁> b₁Ш4

4. c=a₁–b₁=18=2∙9, c₁=9

5. a₁=9, b₁=9

1. a₁=9, b₁=9, k=0

2. a₁= b₁ Ш6

6. (a,b) = 2º∙9=9

Для НОД справедливы следующие свойства:

1) (am,bm)=m(a,b)

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

Доказательство строится, умножая почленно соотношения алгоритма Евклида на m.

2) d – общий делитель чисел a и b

(в частности, ).

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

Учитывая, что и– целые числа, из свойства НОД №1 получаем соотношение , что и требовалось.

□

3) (a,b)=1 (ac,b)=(c,b)

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

a, b, c выполняется (ac,b)\ac, (ac,b)\b (ac,b)\bc(ac,b)\(ac,bc).

По условию теоремы, в силу взаимной простоты a и b (ac,bc)=c, то есть получили (ac,b)\с.

Но (ac,b)\b (ac,b)\(c,b).

С другой стороны, (c,b)\ac, (c,b)\b. (c,b)\(ac,b).

Таким образом, числа (ac,b)и (c,b). взаимно делят друг друга (ac,b)=(c,b).

□

4) (a,b)=1, b\ac b\c.

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

Из теоремы №1 о НОД в силу b\ac, (ac,b)=b.

из свойства НОД № 3 b=(c,b)и тогда из теоремы №1 о НОД b\c.

□

5) Если (a_i, b_j)=1 для , (,)=1.

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

имеем (,) = (,) = (,) = … =.

Аналогично, используя полученное соотношение,

(,) = (,) = … = (,) = 1.

□