Например, пусть и = 40902, v = 24140. На шаге Х2 получаем следующее.

Поэтому решение имеет вид 337 • 40902 - 571 • 24140 = 34 = gcd(40902,24140).

История алгоритма X восходит к трактату Aryabhatiya (499 г. н. э.), авторство которого принадлежит Ариабхата (Aryabhata), жившему в северной Индии. Хотя описание здесь было изложено в весьма зашифрованном виде, более поздние комментаторы, например Бхаскара I (Bhascara I) в 6 веке, сформулировали правило, названное kuttaka ("куттака" или "распылитель"). [См. В. Datta, А. N. Singh, History of Hindu Mathematics 2 (Lahore: Motilal Banarsi Das, 1938), 89-116.] Справедливость алгоритма X следует из соотношений (16) и того обстоятельства, что алгоритм идентичен алгоритму А в смысле выполнения операций с числами из и V3. Подробное доказательство алгоритма X приведено в разделе 1.2.1. Гордон Г. Брэдли (Gordon Н. Bradley) заметил, что если исключить U2,V2iit2, то можно значительно сократить процесс вычислений при вьшолнении алгоритма X; значение Ua может быть определено впоследствии из соотношения uui + vU2 = U3.

В упр. 15 показано, что значения ui, jual, juil и jua] остаются в интервале, ограниченном значениями исходных чисел и и v. Подобным образом может быть обобщен и алгоритм В, который вычисляет наибольший общий делитель, используя свойства чисел, представленных в двоичной системе счисления (упр. 39). Некоторые поучительные обобщения алгоритма X представлены в упр. 18 и 19 в разделе 4.6.1.

Идеи, лежащие в основе алгоритма Евклида, можно также применить для нахождения общего целочисленного решения произвольной системы линейных уравнений с целочисленными коэффициентами. Например, пусть требуется найти все целые числа w, х, у, z, которые удовлетворяют двум уравнениям:

lOw + 3x + 3y + 8z = l, (17)

6w-7x -5z = 2. (18)

Введем новую переменную

[10/3J«; -1- [3/3Ja; -l- [3/3\y + [8/3]г = 3w + x + у + 2z = ti

и используем ее для исключения у. Уравнение (17) примет вид

(10 mod 3)«; -1- (3 mod 3)а; -i- 3ii -l- (8 mod 3)z = w + 3ti +2z = l, (19)

a уравнение (18) останется неизменным. Используем новое уравнение (19) для исключения W, тогда (18) примет вид

6(1 - 3ii - 2z)-7x-5z = 2

т. е.

7х + 18ii + 17г = 4. (20)

Теперь, как и ранее, введем в рассмотрение новую переменную

а; + 2ii + 2г =

и исключим X из уравнения (20):

7<2 + 4ii + Зг = 4. (21)

Таким же способом можно ввести еще одну новую переменную, чтобы исключить переменную z, имеющую наименьший коэффициент:

2i2 + ti + г = is-

Исключение z из уравнения (21) дает

i2 + *1 + 3i3 = 4. (22)

Наконец, используя данное уравнение, исключим *2- После всех этих операций остаются две независимые переменные ti и t. Подставляя их вместо исходных переменных, получаем общее решение:

w= 17- 5ii-14i3,

x = 20 - 5ii - 17i3, 23)

2/ =-55 + Ш1+45i3,

2 = -8+ h+ 7t3.

Другими словами, все целочисленные решения {w,x,y,z) исходных уравнений (17) и (18) получаются из уравнений (23) путем независимой прогонки величин t\ и <з через все целые значения.

Общий метод, проиллюстрированный в приведенном примере, основан на следующей процедуре. Найдем в системе уравнений ненулевой коэффициент с с наименьшим абсолютным значением. Предположим, что он появляется в уравнении вида

схо + cixi -I- • • • -1- CkXk = d; (24)

положим также для простоты, что с > 0. Если с = 1, то воспользуемся этим уравнением для исключения переменной хо из остальных уравнений системы. Затем повторим эту же процедуру по отношению к оставшимся уравнениям системы. (Если уравнений больше не-остается, то вычисления прекращаются и, по существу, получаем общее решение, выражаемое через оставшиеся переменные.) Если с > 1 и если Ci mod с = • • • = с, mod с = О, то проверяем выполнение d mod с = 0; в противном случае целочисленных решений нет. Затем делим обе части уравнения (24) на с и исключаем хо так же, как и в случае, когда с = 1. В итоге, если с > 1 и не все из ci mod с, ...,Ck mod с равны нулю, вводим новую переменную

[c/cjzo -1- Lci/cjxi -1- • • -1- [Cklc\xk = i, (25)

исключаем переменную xq из других уравнений при помощи t и заменяем исходное уравнение (24) уравнением

ct + (ci mod c)xi н-----1- (с, mod c)xk = d. (26)

(Cm. (19) и (21) в рассмотренном выше примере.)

Этот процесс должен завершиться, так как в результате выполнения каждого шага уменьшается либо количество уравнений системы, либо величина наименьшего ненулевого коэффициента системы. Если описанную процедуру применить к уравнению их + vy = 1 для различных целых чисел и и v, то, по существу, буд}т выполняться шаги алгоритма X.

Рассмотренная только что процедура преобразования переменных является простым и достаточно очевидным средством решения систем линейных уравнений с целочисленными коэффициентами, но отнюдь не самым лучшим методом решения такой задачи. Имеются существенные модификации метода, но они выходят за рамки настоящей книги. [См. Henri Cohen, А Course in Computational Algebraic Number Theory (New York: Springer, 1993), Chapter 2.]

Возможно использование алгоритма Евклида с Гауссовыми целыми числами и + ги, а также с некоторыми другими квадратичными числовыми полями. (См., например, А. Hurwitz, Acta Math. 11 (1887), 187-200; Е. Kaltofen, Н. Rolletschek, Math. Сотр. 53 (1989), 697-720; A. Knopfmacher, J. Knopfmacher, BIT 31 (1991), 286-292.)

Вычисление с высокой точностью. Если и и v - очень большие целые числа, требующие представления с многократной точностью, то бинарный метод (алгоритм В) служит простым и достаточно эффективным методом вычисления наибольшего общего делителя этих чисел, так как в нем при вычислениях используются только операции вычитания и сдвига.

Напротив, алгоритм Евклида представляется значительно менее привлекательным, так как на шаге А2 требуется разделить с многократной точностью число и на число V. Но на самом деле это не является препятствием для применения алгоритма Евклида, поскольку, как будет доказано в разделе 4.5.3, частное [u/uj почти всегда очень мало. Например, для случайных входных данных частное [u/v\ будет меньше 1 ООО примерно в 99.856% случаев. Поэтому [u/v\ и {и mod v) почти всегда можно найти при помощи вычислений, выполняемых с однократной точностью в сочетании ср сравнительно простой операцией вычисления u-qv, где q - число, представленное с однократной точностью. Далее, если окажется, что и намного больше v (к примеру, в таком виде могут задаваться входные данные), трудно представить, что частное q может оказаться большим, так как алгоритм Евклида, если заменить и на и mod и, в этом случае выпоДняется достаточно успешно.

Значительного увеличения скорости выполнения алгоритма Евклида при работе с числами высокой точности можно добиться при помощи метода, предложенного Д. Г. Лемером (D. Н. Lehmer) [АММ 45 (1938), 227-233]. Оперируя только старшими разрядами больших чисел, можно основную часть вычислений вьшолнять с однократной точностью, значительно сокращая таким образом количество операций, которые необходимо вьшолнять с многократной точностью. Идея заключается в экономии времени за счет выполнения "виртуальных" вычислений вместо фактических.

Например, рассмотрим два восьмизначных числа и = 27182818 и и = 10000000, предполагая, что имеется компьютер с четырехразрядными словами. Пусть и = 2718, v = 1001, и" = 2719, v" = 1000; тогда u/v и u"/v" являются приближениями