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

Этот вариант создан специально для реализации на ЭВМ. В нем учитывается, что операция деления на число 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

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.

□