AOP_Tom2 (1021737), страница 103
Текст из файла (страница 103)
Это должно рано или поздно произойти, потому что, если разность будет равна единице, то единица будет делить предыдущее вычитаемое. Теперь положим, что Š— положительный остаток от деления числа А на С; пусть Š— положительный остаток от деления числа С на число Е и пусть Е делит Е. Так как Е делит Е, а Е делит С вЂ” Е, Е также делит С вЂ” Е. Но оно делит и самое себя, поэтому Е делит С, а С делит А — Е; поэтому Е также делит А — Е, но оно делит и Е; поэтому Е делит А. Следовательно, Г является общим делителем чисел А н С. Теперь я утверждаю, что оно является и наибольшим делителем.
Действительно, если Š— не наибольший общий делитель чисел А и С, то найдется большее число, которое будет делить оба зги числа. Пусть таким числом будет С. Так ках число С делит число С, а число С делит А — Е, то С также делит число А — Е. Число С делит также все число А, поэтому оно делит и остаток Е.
Но Е делит С вЂ” Е, поэтому С такясе делит С вЂ” Е. А число С также делит все число С, так что оно делит Н остаток Е; таким образом, большее число делит меныпее, а зто невозможно. Таким образом, нет такого числа, большего, чем Р, которое бы делило А н С; значит, число К является наибольшим общим делителем. Следствие. Это рассуждение делает очевидным предложение, что всякое число, делящее два числа, делит и их наибольший общий делитель. Ч.
Т. Д. Формулировка Евклида упрощена здесь в одном немаловажном аспекте. Греческие математики не считали единицу "делителем" другого положительного числа. Два положительных целых числа были либо оба равны единице, либо взаимно просты, либо имели наибольший общий делитель. Фактически единица даже не считалась числом, а нуль, конечно, вообще не существовал. Эти довольно нескладные соглашения были причиной того, что Евклид должен был дублировать значительную часть своих рассуждений, и он дал два отдельных предложения, каждое из которых по существу сходно с вышеприведенным.
В своем доказательстве Евклид впервые предлагает повторно вычитать для каждой пары текущих значений меньшее число из большего до тех пор, пока в результате получатся два числа, одно из которых кратно другому. Но при доказательстве он фактически берет остаток от деления одного числа на другое, а так как понятие нуля отсутствовало, он не может говорить об остатке, когда одно число делит другое. Поэтому резонно заявить, что оп рассматривает каждое деление (а не каждое вычитание в отдельности) как один шаг алгоритма,н, следовательно, "аутентичное' изложение его алгоритма выглядит следующим. Алгоритм Е (Оригинальный алгоритм Евклида).
По двум целым числам Л и С, ббльшим единицы, этот алгоритм находит их наибольший общий делитель. Е1. [Л делится на С?] Если С делит Л, то алгоритм заканчивается, давая в качестве результата число С. Е2. [Заменить Л остатком.] Если Л пюб С равно единице, то заданные числа взаимно просты, поэтому алгоритм заканчивается. В противном случае заменить пару значений (Л, С) парой (С, Л шос1 С) и вернуться и шагу Е1. 1 "Доказательство" Евклида, приведенное выше, представляет особый интерес, так как оно в действительности совсем не является доказательством! Евклид проверяет результат алгоритма только тогда, когда шаг Е1 выполняется либо один раз, либо три раза. Он, безусловно, должен был понимать, что шаг Е1 может выполняться больше трех раэ, хотя и не упоминает о такой возможности.
Не имея представления о доказательстве при помощи математической индукции, он мог привести доказательство только для конечного числа случаев. (Фактически, желая доказать теорему для общего случая и, он рассматривал только частный случай и = 3.) Хотя алгоритм Евклида заслуженно известен своим большим вкладом в искусство логической дедукции, приемы, применяемые в строгих доказательствах по индукции, были открыты только спустя многие столетия, а ключевые идеи, используемые для доказательства справедливости алгорипьмов, становятся по-настоящему понятными только сейчас. (Полное доказательство алгоритма Евклида, а также краткое обсуждение основной процедуры доказательства алгоритмов изложены в разделе 1.2.1.) Следует отметить, что этот алгоритм нахождения наибольшего общего делителя был выбран Евклидом в качестве первого шага в его изложении теории чисел.
И в наши дни во многих учебниках все еще используется тот же порядок изложения. Евклид двл, кроме того, метод (предложение 34) нахождения наименьшего общего кратного двух целых чисел и и в, а именно: разделить и на ба(и,в) и затем умножить результат на ьй это равносильно соотношению (10). Если пренебречь предубеждением Евклида против чисел О и 1, то алгоритм Е можно переформулировать следующим образом.
Алгоритм А (Ллавришм Евклида в современной редакции). По данным неотрицательным целым числам и и г этот алгоритм находит их наибольший общий делитель. [Замечание. Наибольший общий делитель произвольных целых чисел и и г можно получить с учетом соотношений (2) и (3), применив алгоритм к ]и[ и [е[.) А1. [г = О?] Если г = О, то выполнение алгоритма заканчивается, а в качестве результата возвращается число и. А2.
[Взять и шоб ш] Присвоить г < — и шоб е, и <- и, и < — г и вернуться к шагу А1. (В результате выполняемых на этом шаге операций значение г уменьшается, значение кой(и, о) остается неизменным.) 1 Например, можно вычислить Ясд(40902, 24140) следующим образом: Нсд(40902, 24140) = Нсб(24140, 16762) = Ясд(16762, 7378) = Ясб(7378, 2006) = Ясб(2006, 1360) = Ясб(1360, 646) = Ясб(646, 68) = Нсб(68, 34) = Ясй(34, О) = 34. Справедливость алгоритма А легко доказать из соотношения (4) и уравнения (13) Нсо(и, и) = Нсб(и, и — Чи) для любого целого числа Ч.
Уравнение (13) выполняется потому, что любой общий делитель чисел и и е является делителем как е, так и и — аи, и наоборот, любой общий делитель чисел и и и — ои должен делить оба числа и и е. В следующей И1Х-программе показано, что алгоритм А может быть легко реализован на компьютере. Программа А (Алгоритм Евклида). Положим, что и и и — неотрицательные целые числа однократной точности, помещенные в ячейки 0 и Ч соответственно; эта программа помещает Ясб(и, и) в ячейку гА.
РРХ 0 ЛИР 2Г 1Н ЯТХ Ч ЯНАХ 5 01Ч Ч 2НЫА Ч 1ХНХ 1В 1 гХе-и. 1 Т и ~.'— гХ. Т гАХ +- гА. Т гХ е- гАХ мой ь. 1 +Т гА е- е. 1+ Т Выполнено, если гХ = О. 1 Время выполнения программы составляет 19Т + 6 циклов, где Т вЂ” число выполненных операций деления. Рассуждения, приведенные в разделе 4.5.3, показывают, что в случае, когда и и и независимо и равномерно распределены в интервале 1 < и,е < )Ч, среднее значение Т можно приблизительно представить в виде Т = 0,8427661п1Ч+ 0.06. Виыарный метод. После стольких столетий применения почтенного алгоритма Евклида несколько неожиданным оказалось то, что он не всегда является лучшим способом определения наибольшего общего делителя. В 1961 году Джозеф Стейн (ЛозеГ 81еш) предложил совершенно другой алгоритм нахождения наибольшего общего делителя, ориентированный, прежде всего, на двоичную арифметику [см.
3. Сошр. РБ1м. 1 (1967), 397-405]. Этому новому алгоритму совершенно не нужны команды, выполняющие операции деления. Основанныи исключительно на операциях вычитания, он проверяет, четно ли число, и делит пополам четные числа (что соответствует в двоичной арифметике сдвигу вправо). Бинарный алгоритм нахождения наибольшего общего делителя основан на четырех простых фактах относительно положительных целых чисел и и и.
а) Если и и и оба четны, то Нсд(и, е) = 2 Ясг)(и/2, е/2) [см. уравнение (8)]. Ъ) Если и четно, а и нечетно, то Ясс((и, е) = Ясб(и/2, е) [см. уравнение (6)]. с) Как и в алгоритме Евклида, Ясг)(и, с) = йсб(и — и, е) [см. уравнения (13) и (2)]. 6) Если и и е оба нечетиы, то и — и четно и [и — и[ < шах(и, и). Алгоритм В (Бинарный алгорипьм нахождения наибольшего общего делителя). ПО данным целым числам и и о этот алгоритм (рис.
9) находит наибольший общий делитель, В1. (Найти степень 2.] Присвоить к +- О, затем повторно присваивать Ж» — к+ 1, и < — и/2, о +- о/2 нуль или более раз до тех пор, пока оба числа и и о станут нечетными. В2. [Начальная установка.] (Исходные значения чисел и и о уже разделены на 2», и по крайней мере одно из текущих значений нечетко.) Если нечетио и, то присвоить 1+- — о и перейти к шагу В4. В противном случае присвоить 1» — и. ВЗ. (Уменьшить 1 наполовину.] (Здесь 1 четко и ие нуль.) Присвоить 1» — 1/2. В4. [1 четно7] Если 1 четяо, то вернуться к шагу ВЗ. В5. [Установить шах(и, о) заиово.] Если 1 > О, то присвоить и <- 1, в противном случае присвоить о < — — 1. (Большее из чисел и и о заменяется на [1( эа исключением, возможно, первого выполнения этого шага.) В6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
