Отсюда, например, следует, что наибольший общий делитель числа и = 7000 = 2 • 5 • 7, а числа v = 4400 = 2 5 • 11 равен 2""(2) 5min(3,2) yminCbo) min(o,i) 2 • 5 = 200. Наименьшее общее кратное тех же чисел равно 2 • 5 • 7 11 = 154000.

Из формул (6) и (7) легко получить ряд основных тождеств, относящихся к наибольшему общему делителю и наименьшему общему кратному:

gcd{u,v)w - - gcd(uw,vw) при w >0; (8)

lcm{u,v)w = lcm{uw,vw) при ш > 0; (9)

и V = gcd{u,v) lcm{u,v) при u,u > 0; (10)

gcd(lcm(u,u),lcm(u,it;)) = lcm(u,gcd(u,tt;)); (И)

lcm(gcd(u,u),gcd(u,tt;)) = gcd(u,lcm(i;,tt;)). (12)

Два последних равенства являются аналогами "дистрибутивного закона" uv + uw = u{v + w). Соотношение (10) сводит вычисление gcd(u,u) к вычислению lcm(u,u) и наоборот.

Алгоритм Евклида. Хотя соотношение (6) очень интересно в теоретическом аспекте, для практического вычисления наибольшего общего делителя оно бесполезно, так как для этого требуется сначала найти разложение чисел и и v на простые множители. На сегодняшний день неизвестны способы очень быстрого поиска простых множителей для целых чисел (см. раздел 4.5.4). К счастью, наибольший общий делитель двух целых чисел может быть эффективно найден без разложения чисел на простые множители. Такой метод был открыт более 2 250 лет тому назад-это алгоритм Евклида, который уже подробно рассматривался в разделах 1.1 и 1.2.1.

Алгоритм Евклида находится в книге 7 его Начал (ок. 300 г. до н. э.), предложения 1 и 2, но, вероятно, он не был придаман Евклидом. Некоторые ученые предполагают, что данный метод был известен за 200 лет до этого, по крайней мере в форме, использующей вычитания, и почти наверняка этот алгоритм был известен Евдоксу (ок. 375 г. до н. э.); см. К. von Fritz, Ann. Math. (2) 46 (1945), 242-264. Аристотель (ок. 330 г. до н. э.) упомянут в этой книге в связи с рассматриваемой темой, 158Ь, 29-35. Тем не менее осталось очень мало свидетельств столь ранней истории этого алгоритма [см. W. R. Knorr, The Evolution of the Euclidean Elements (Dordrecht," 1975)].

Алгоритм Евклида можно назвать дедушкой всех алгоритмов, так как он самый старый из всех нетривиальных алгоритмов, дошедших до наших дней. (Эту честь мог бы, пожалуй, оспаривать древнеегипетский метод умножения, в основу которого положен метод удваивания и сложения и на котором базируется эффективный метод вычисления п-х степеней, рассматриваемый в разделе 4.6.3. Но в египетских папирусах просто приведены примеры, не носящие законченного систематического характера, и эти примеры во всяком случае не изложены систематически. Поэто.му египетский метод не совсем заслуживает названия "алгоритм". Известно также несколько древних вавилонских методов, применяемых для такого рода задач, как решение специальных систем квадратных уравнений с двумя неизвестными. Это настоящие алгоритмы, а не просто частные решения уравнений для определенных входных параметров. Хотя вавилоняне постоянно сопровождали изложение каждого метода примером для частных значений входных параметров, они в сопроводительном тексте регулярно приводили объяснение основной процедуры. [См. D. Е. Knuth, САСМ

15 (1972), 671-677; 19 (1976), 108.] Многие из этих алгоритмов были известны за 1 500 лет до Евклида и являются наиболее ранними образцами записанных алгоритмов. Однако они не выдерживают сравнения с алгоритмом Евклида, поскольку в них отсутствуют итерации. Именно поэтому они были вытеснены современными алгебраическими методами.)

В свете важности алгоритма Евклида как в историческом так и в теоретическом аспектах посмотрим, как его трактовал сам Евклид. Перефразировав Евклида и использовав современную терминологию, мы можем сказать, что он писал примерно следующее.

Предложение. Для данных двух положительных целых чисел найти их наибольший общий делитель.

Пусть А и С-два заданных положительных целых числа; требуется найти их наибольший общий делитель. Если число А делится на С, то число С есть общий делитель чисел С и А, поскольку оно делит самое себя. И очевидно, что оно будет и наибольшим делителем, поскольку нет числа, большего, чем число С, которое бы делило С.

Но если С не делит число А, то будем непрерывно вычитать меньшее из чисел А, С из большего до тех пор, пока не получим число, которое нацело делит предыдущее вычитаемое. Это должно рано или поздно произойти, потому что, если разность будет равна единице, то единица будет делить предыдущее вычитаемое.

Теперь положим, что Е - положительный остаток от деления числа А на С; пусть F - положительный остаток от деления числа С на число Е и пусть F делит Е. Так как F делит Е, а Е делит С - F, F также делит С - F. Но оно делит и самое себя, поэтому F делит С, а С делит А - Е; поэтому F также делит А - Е,ио оно делит и Е; поэтому F делит А. Следовательно, F является общим делителем чисел А и С.

Теперь я утверждаю, что оно является и наибольшим делителем. Действительно, если F - не наибольший общий делитель чисел А и С. то найдется большее число, которое будет делить оба эти числа. Пусть таким числом будет G.

Так как число G делит число С, а число С делит A - E,toG также делит число А - Е. Число G делит также все число А, поэтому оно делит и остаток Е. Но Е делит C - F, поэтому G также делит С - F. А число G также делит все число С, так что оно делит р остаток F; таким образом, большее число делит меньшее, а это невозможно.

Таким образом, нет такого числа, большего, чем F, которое бы делило А и С; значит, число F является наибольшим общим делителем.

Следствие. Это рассуждение делает очевидным предложение, что всякое число, делящее два числа, делит и их наибольший общий делитель. Ч. Т. Д.

Формулировка Евклида упрощена здесь в одном немаловажном аспекте. Греческие математики не считали единицу "делителем" другого положительного числа. Два положительных целых числа были либо оба равны единице, либо взаимно просты, либо имели наибольший общий делитель. Фактически единица даже не считалась числом, а нуль, конечно, вообще не существовал. Эти довольно нескладные соглашения были причиной того, что Евклид должен был дублировать значительную часть своих рассуждений, и он дал два отдельных предложения, каждое из которых по существу сходно с вышеприведенным.

В своем доказательстве Евклид впервые предлагает повторно вычитать для каждой пары текущих значений меньшее число из большего до тех пор, пока в

результате получатся два числа, одно из которых кратно другому. Но при доказательстве он фактически берет остаток от деления одного числа на другое, а так как понятие нуля отсутствовало, он не может говорить об остатке, когда одно число делит другое. Поэтому резонно заявить, что он рассматривает каждое деление (а не каждое вычитание в отдельности) как один шаг алгоритма, и, следовательно, "аутентичное" изложение его алгоритма выглядит следующим.

Алгоритм Е (Оригинальный алгоритм Евклида). По двум целым числам А и С, большим единицы, этот алгоритм находит их наибольший общий делитель.

Е1. [А делится на С?] Если С делит А, то алгоритм заканчивается, давая в качестве результата число С.

Е2. [Заменить А остатком.] Если А mod С равно единице, то заданные числа взаимно просты, поэтому алгоритм заканчивается. В противном случае заменить пару значений (А, С) парой (С, А mod С) и вернуться к шагу El.

"Доказательство" Евклида, приведенное выше, представляет особый интерес, так как оно в действительности совсем не является доказательством! Евклид проверяет результат алгоритма только тогда, когда шаг Е1 вьшолняется либо один раз, либо три раза. Он, безусловно, должен был понимать, что шаг Е1 может выполняться больше трех раз, хотя и не упоминает о такой возможности. Не имея представления о доказательстве при помощи математической индукции, он мог привести доказательство только для конечного числа случаев. (Фактически, желая доказать теорему для общего случая п, он рассматривал только частный случай п = 3.) Хотя алгоритм Евклида заслуженно известен своим большим вкладом в искусство логической дедукции, приемы, применяемые в строгих доказательствах по индукции, были открыты только спустя многие столетия, а ключевые идеи, используемые для доказательства справедливости алгоритмов, становятся по-настоящему понятными только сейчас. (Полное доказательство алгоритма Евклида, а также краткое обсуждение основной процедуры доказательства алгоритмов изложены в разделе 1.2.1.)

Следует отметить, что этот алгоритм нахождения наибольшего общего делителя был выбран Евклидом в качестве первого шага в его изложении теории чисел. И в наши дни во многих учебниках все еще используется тот же порядок изложения. Евклид дал, кроме того, метод (предложение 34) нахождения наименьшего общего кратного двух целых чисел и и и, а именно: разделить и на gcd(u,u) и затем умножить результат на v\ это равносильно соотношению (10).

Если пренебречь предубеждением Евклида против чисел О и 1, то алгоритм Е можно переформулировать следующим образом.

Алгоритм А (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам и и г; этот алгоритм находит их наибольший общий делитель. [Замечание. Наибольший общий делитель произвольных целых чисел и и v можно получить с учетом соотношений (2) и (3), применив алгоритм к и и \v\.)

Al. [v = О?] Если и = О, то выполнение алгоритма заканчивается, а в качестве результата возвращается число и.

А2. [Взять и mod v.] Присвоить г <- и mod v, и <г- v, v <г- г и вернуться к шагу А1. (В результате выполняемых на этом шаге операций значение v уменьшается, значение gcd(u,v) остается неизменным.)