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

Всего пять шагов – и мы готовы выписать ответ. НОД(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;