Алгоритм Евклида: итерационный и рекурсивный

Алгоритм, вероятно, был обнаружен не Евклидом – он лишь обобщил результаты более ранних математиков в своей книге «Начала» [3]. Б. Л. Ван Дер Варден предполагает, что Книга VII, в которой впервые был опубликован алгоритм, берет начало в учебнике по теории чисел, написанного математиками школы Пифагора. Алгоритм, вероятно, был известен Евдоксу Книдскому (около 375 г. до н.э.), однако он может даже предшествовать Евдоксу, судя по использованию термина ангифарез (обратное вычитание) в работах Евклида и Аристотеля.
Спустя столетия алгоритм Евклида был открыт независимо как в Индии, так и в Китае [4], главным образом, для решения диофантовых уравнений, возникающих в астрономии, и составления точных календарей. В Европе его также использовали для получения непрерывных дробей. Расширенный алгоритм Евклида был опубликован английским математиком Николасом Сондерсоном, который приписал его Роджеру Котсу, и описан как способ эффективного вычисления непрерывных дробей [6].
В XIX веке алгоритм Евклида получил новое применение. В 1815 году Карл Гаусс использовал алгоритм для демонстрации уникальной факторизации гауссовых целых чисел, хотя его работа была впервые опубликована в 1832 году. Гаусс упомянул алгоритм в своей книге «Disquisitiones Arithmeticae» (опубликованной в 1801 г.), но только как метод для получения непрерывных дробей. Петер Густав Лежен Дирихле, по-видимому, был первым, кто описал алгоритм Евклида в качестве основы для большей части теории чисел. Дирихле отметил, что многие результаты теории чисел, такие как уникальная факторизация, будут справедливы для любой другой системы чисел, к которой может быть применен алгоритм Евклида. Лекции Дирихле по теории чисел были отредактированы и расширены Ричардом Дедекиндом, который использовал алгоритм Евклида для изучения алгебраических целых чисел, нового типа чисел. Например, Дедекинд был первым, кто доказал теорему Ферма о сумме двух квадратов, используя уникальную факторизацию гауссовых целых чисел [7]. Дедекинд также определил концепцию евклидовой области, системы счисления, в которой может быть определена обобщенная версия алгоритма Евклида.
Большинство приложений алгоритма Евклида были получены также в XIX веке. В 1829 году Чарльз Штурм показал, что алгоритм полезен в ряде Штурма для подсчета действительных корней многочленов в любом заданном интервале [7].
Описание алгоритма Евклида
Любое целое число a представляется единственным способом через натуральное число b в форме
a=bq+r; 0≤r<b (1)
В этом случае q называют неполным частным от деления a на b, а r остатком. Если r=0, то говорят, что a кратно b или что b является делителем числа a.
Теперь можно получить алгоритм нахождения наибольшего общего делителя положительных целых чисел a и b. Он традиционно обозначает gcd(a,b) (от англ. Greatest Common Divisor, рус. Наибольший Общий Делитель).
Теорема: Если для целых чисел a, b, q, r выполняется равенство, (1) то совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и r.
Доказательство: Пусть k – общий делитель чисел a и b. Это значит, что есть такие целые q1 и q2, для которых a=kq1 и b=kq2. Тогда kq1=kq2q+r или r=kq1-q2q. Последнее равенство доказывает, что k является делителем числа r. Аналогично доказывается, что любой общий делитель чисел b и r является также делителем числа a. Таким образом, множество общих делителей чисел a и b совпадает с множеством общих делителей чисел b и r. В частности, совпадают их НОД: gcd(a,b) = gcd(b,r).
Тогда для неотрицательных целых чисел можно записать ряд следующих равенств:
a=bq1+r1, 0<r1<b
b=r1q2+r2, 0<r2<r1 (2)
r1=r2q3+r3, 0<r3<r2
и т.д.
Таким образом, совокупность остатков получается убывающей: r1>r2>r3>… Но все эти остатки положительны и меньше b. А последовательность убывающих натуральных чисел, большее из которых меньше b, не может состоять больше, чем из b чисел. Значит, на каком-то шаге будет получен нулевой остаток: rn-1=rnqn+1+0.
Таким образом, совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и r1, которая совпадает с совокупностью общих делителей чисел r1 и r2 и т.д., пока не будет получена пара rn и 0. НОД последней пары – это rn. Теорема доказана. Последнее означает, что НОД пары натуральных чисел a и b равен последнему отличному от нуля остатку в приведённом выше ряду (2).
Алгоритм, описанный выше, работает как для положительных чисел, так и в том случае, если одно из чисел натуральное, а другое равно нулю. Однако если хотя бы одно из чисел отрицательно, для нахождения НОД можно использовать следующее свойство [1]:
gcda,b=gcd⁡(a,b) (3)
Описание расширенного алгоритма Евклида
Теперь можно выразить НОД натуральных чисел a и b в виде линейной комбинации этих чисел (соотношения Безу). То есть необходимо найти такие числа x и y, что
x∙a+y∙b=gcd⁡(a,b) (4)
Если b=0, то такое разложение получить довольно просто. Достаточно взять x=1, а в качестве значения y можно выбрать любое число, например ноль:
1∙a+0∙0=gcd⁡(a,0) (5)
Пусть теперь b≠0. Как уже известно из доказанной выше теоремы, в этом случае gcda,b=gcd⁡(b,a mod b).
Поскольку a mod b=a-q∙b, где q=ab — целая часть от деления a на b, то осталось для gcd⁡(b,a mod b) найти разложение, аналогичное (4).
x1∙b+y1∙a-q∙b=gcdb,a mod b=gcd⁡(a,b)
После преобразования последнего равенства получается
y1∙a+x1-q∙y1∙b=gcd⁡(a,b) (6)
Равенства (4) и (6) должны выполняться при любых значениях a и b. Это будет происходить, если задать
408241575565 (7)
00 (7)
x=y1
y=x1-q∙y1
Равенства (5) и (7) позволяют организовать рекурсивное вычисление коэффициентов из формулы (4). Более того, коэффициенты x и y можно сделать целыми числами, поскольку при их нахождении используются только операции умножения, вычитания и деление нацело (для вычисления q), а начальные значения x и y, как следует из (5), можно выбрать целочисленными. При этом числа x и y не обязательно будут натуральными.
В вычислении НОД двух натуральных чисел и его представления в виде линейной комбинации (4) исходных чисел описанным выше способом состоит суть расширенного алгоритма Евклида [2].