Расширенный алгоритм Евклида

Пусть есть два отрезка. Их длины a и b – целые числа (далее, говоря о числах, считаем их всегда целыми). Скажем, a=2322, а b=654.

Если, например, отложить на прямой отрезок a, затем, в обратном направлении, три раза b, то получим отрезок длиной 360 (рис. 1.21). Действительно, a+b·(–3)=2322+654·(–3)=360.

Рис. 1.21. Пример откладывания на прямой отрезков длины a и b

Можно получить и отрезок меньшей длины. Действуем так: a·2+b·(–7)= 2322·2+654·(–7)=66 – два раза откладываем отрезок a и семь раз отрезок b в обратном направлении. Возникает, как минимум, четыре вопроса.

1. Какую наименьшую длину удастся получить, «орудуя» заданными отрезками a и b?

2. Как это сделать, сколько раз взять отрезок a и сколько раз отрезок b?

3. Какой длины отрезки отмеряются с помощью a и b?

4. Если отрезок заданной длины отмеряется, то, как это сделать?

Первый вопрос

Итак, отрезок какой наименьшей длины можно получить, используя отрезки a и b?

Эксперимент. Пусть a и b – положительные, фиксированные, а x и y –произвольные целые числа. Напишем процедуру, которая перебирает числа вида a·x+b·y и находит среди них минимальное положительное.

Procedure Small (a,b:Integer; Var min:Integer);

Const k=500;

Var x,y,t:Integer;

Begin

min:=a;

For x:=-k To k Do

For y:=-k To k Do Begin

t:=a*x+b*y;

If (t>0)And(t<min) Then min:=t;

End;

End;

Перебор ограничен константой k и выглядит несколько искусственным, но он достаточен для генерации идеи (гипотезы). Экспериментируя, заполняем таблицу (табл. 1.6).

Примечание. Убедитесь, что данные в табл. 1.6 не изменятся и при больших k, а гипотеза будет верна и для других a и b.

Таблица 1.6

a	b	min
10	15	5
18	24	6
105	165	15
64	32	32
17	53	1
9	55	1
54	45	9
2322	654	6

Гипотеза. Обозначим множество всех чисел вида a·x+b·y буквой P. Возьмём min – наименьшее положительное число из P. Оказывается, это наибольший общий делитель a и b.

Второй вопрос

Как отмерить отрезок наименьшей длины? Сколько раз для этого взять отрезок a и сколько раз отрезок b?

Почти всегда срабатывает метод «грубой силы» – перебор. Эта задача не исключение. Отрезки a и b даны. Наименьшую длину d=НОД(a,b) находим по алгоритму Евклида. После этого подбираем целые x и y такие, чтобы a·x+b·y=d. Для этого ищем целое x такое, при котором и y=(d–a·x)/b также целое. Начинаем с x=0, а затем «движемся» от него по числовой прямой, в двух направлениях одновременно, с шагом 1.

Procedure Simple(a,b,d:Integer; Var x,y:Integer);

Var xn,xp:Integer;

Begin

xp:=0; xn:=0;

While ((d-a*xp) Mod b<>0) And ((d-a*xn) Mod b<>0) Do

Begin

xp:=xp+1;

xn:=xn-1;

End;

If (d-a*xp) Mod b=0 Then x:=xp Else x:=xn;

y:=(d-a*x)Div b;

End;

Цикл гарантированно завершится. Ведь искомое x точно есть, либо справа от нуля, либо слева.

Однако, узнать и сам НОД(a,b), и его представление в виде a·x+b·y, где x и y – целые числа, можно одновременно и без перебора. Для этого требуется изменить (расширить) стандартную версию алгоритма Евклида.

Расширенный итеративный алгоритм Евклида

Нам предстоит дополнить знакомую логику реализации алгоритма Евклида.

Procedure Euclid (a,b:Integer; Var d:Integer);

Var r:Integer;

Begin

While b>0 Do Begin

r:=a Mod b;

a:=b;

b:=r;

End;

d:=a;

End;

В этой логике, идя по цепочке остатков от деления, мы приближаемся к цели – находим наибольший общий делитель. Например, 2322, 654, 360, 294, 66, 30, 6, 0. Последний ненулевой остаток и есть наибольший общий делитель.

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

= ·1+ ·0, = ·0+ ·1.

Вопрос. Допустим, мы знаем для некоторых чисел a и b, как их представить с помощью и :

a= ·x_a+ ·y_a, b= ·x_b+ ·y_b.

Как найти такое же представление для остатка r от деления а на b?

Ответ. Имеем a=q∙b+r, 0≤r<b. Отсюда,

r=a-q∙b=( ·x_a+ ·y_a)-q∙( ·x_b+ ·y_b)= ·(x_a-q∙x_b)+ ·(y_a-q∙y_b),

или

r= ·x_r+ ·y_r,

где

x_r=x_a-q∙x_b, y_r=y_a-q∙y_b.

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

Пример. Пусть a=2322, b=654. Результаты вычислений показаны в табл. 1.7. Первый столбик – это остатки от деления r. Второй – целые части q. Третий и чётвёртый – искомые множители x и y.

В первые две строки помещаем исходные числа и их тривиальные представления. Каждую следующую строку-представление строим по двум предыдущим. Из верхней вычитаем нижнюю, помноженную на q.

Таблица 1.7

r	q	x	y
2322		1	0
654	3	0	1
360	1	1	-3
294	1	-1	4
66	4	2	-7
30	2	-9	32
6	5	20	-71

Всего пять шагов – и мы готовы выписать ответ. НОД(2322, 654) = 6 = 2322·20+654·(-71). То есть. Во-первых, минимальная длина, которую можно отмерить отрезками a=2322 и b=654, равна 6. Во-вторых, для этого нужно отложить 20 раз a, и в обратном направлении 71 раз b.

Procedure ExEuclid (a,b:Integer; Var d,x,y:Integer);

Var r,q,xa,ya,xb,yb,xr,yr:Integer;

Begin

{На старте в цепочке два числа. Это их очевидные представления.}

xa:=1; ya:=0;

xb:=0; yb:=1;

While b>0 Do Begin

{Вычисляем очередной остаток.}

r:=a Mod b;

{А также его представление.}

q:=a Div b;

xr:=xa-q*xb;

yr:=ya-q*yb;

{Цепочка «вырастает» ещё на одно число. Смещаем a и b на её конец. Запоминать то, что было до, нет необходимости. Теперь в роли a будет b, в роли b будет r.}

a:=b;

xa:=xb; ya:=yb;

b:=r;

xb:=xr; yb:=yr;

End;

{После цикла в a и b хранятся последние числа полной цепочки. а – ненулевое. Оно-то нам и требуется, вместе со своим представлением.}

d:=a;

x:=xa; y:=ya;

End;