Пункт 4. Алгоритм Евклида.

Слово "алгоритм" является русской транскрипцией латинизированного имени выдающегося арабского математика ал-Хорезми Абу Абдуллы Мухаммеда ибн ал-Маджуси (787 - ок.850) и означает в современном смысле некоторые правила, список инструкций или команд, выполняя которые, некто (быть может, тупой, но усердный) достигнет требуемого результата. В этом пункте я расскажу алгоритм, позволяющий по заданным натуральным числам a и b находить их наибольший общий делитель. Считается, что этот алгоритм придумал самый влиятельный математик всех времен и народов - Евклид, он изложен в IX книге его знаменитых "Начал".

Отступление "Панегирик Евклиду"

Не могу удержаться от небольшого исторического отступления про Евклида. О его жизни мы не имеем никаких достоверных сведений, может быть, даже, он не был реальной исторической личностью, а являлся коллективным псевдонимом некоей группы Александрийских математиков, типа Николя Бурбаки. Если он жил, то он жил во времена Птолемея Первого (306 - 283), которому, согласно преданию, он надерзил словами "К геометрии нет царской дороги". Но Птолемеи сознательно культивировали науку и культуру в Александрии, поэтому все эти закидоны своих ученых пропускали мимо ушей.

Наиболее знаменитое и выдающееся произведение Евклида - тринадцать книг его "Начал", но есть еще и другие мелкие опусы. Мы не знаем, какая часть этих трудов принадлежит самому Евклиду и какую часть составляют компиляции, но в этих трудах проявляется поразительная проницательность и дальновидность. Это первые математические труды, которые дошли до нас от древних греков полностью. В истории Западного мира "Начала", после Библии, - наибольшее число раз изданная и более всего изучавшаяся книга. Большая часть нашей школьной геометрии заимствована буквально из первых шести книг "Начал", традиция Евклида до сих пор тяготеет над нашим элементарным обучением. Для профессионального математика эти книги все еще обладают неотразимым очарованием, а их логическое дедуктивное построение повлияло на сам способ научного мышления больше, чем какое бы то ни было другое произведение. Слава Птолемеям! Честь и хвала Евклиду! Идут пионеры - Салют "Началам"!

Панегирик окончен.

Пусть даны два числа a и b; a ³ 0, b ³ 0, считаем, что a > b. Символом := в записи алгоритма обозначаем присваивание. Алгоритм:

1. Ввести a и b.

2. Если b = 0, то Ответ: а. Конец.

3. Заменить r:= "остаток от деления а на b ", а:= b, b:= r.

4. Идти на 2.

Как и почему исполнение этого коротенького набора инструкций приводит к нахождению наибольшего общего делителя мы выясним чуть позже, сейчас же хочется сказать несколько слов про сам алгоритм. Внимательное разглядывание и пошаговое выполнение алгоритма Евклида убеждают в его, выражаясь словами иконописца Феофана Грека, "простоте без пестроты". Я очень сожалею, что в тексте невозможно проиллюстрировать работу алгоритма на греческий лад - греки стирали отрезки, нарисованные на песке. У лектора в аудитории в руках мел и тряпка, он может показать этот живой процесс на доске, а вам, дорогие читатели, прийдется довольствоваться застывшим рис. 3:

Рис. 3

В современной буквенной записи, кочующей из одного учебника в другой, алгоритм Евклида выглядит так: a > b; a, b Î Z.

a = bq 1 + r 1 b = r 1 q 2 + r 2 r 1 = r 2 q 3 + r 3 r 2 = r 3 q 4 + r 4	0 £ r 1 < b 0 £ r 2 < r 1 0 £ r 3 < r 2 0 £ r 4 < r 3	Экзаменатор, настойчиво внушающий студенту мысль об ошибочности решения студента явиться на экзамен с невыученным алгоритмом Евклида.
· · · · · · · · ·
r n -3 = r n -2 q n -1 + r n -1 r n -2 = r n -1 q n + r n r n -1 = r n q n +1	0 £ r n -1 < r n -2 0 £ r n < r n -1 r n +1 = 0

Имеем: b > r ₁ > r ₂ >... > r _n > 0, следовательно процесс оборвется максимум через b шагов. Очень интересный и практически важный народохозяйственный вопрос о том, когда алгоритм Евклида работает особенно долго, а когда справляется с работой молниеносно, мы рассмотрим в этой книжке чуть позже. Давайте сейчас покажем, что r _n = (a, b). Просмотрим последовательно равенства сверху вниз: всякий делитель а и b делит r ₁ , r ₂ ,..., r _n . Если же просматривать эту цепочку равенств от последнего к первому, то видно, что r _n | r _{n -1} , r _n | r _{n -2} , и т.д., т.е. r _n делит а и b. Поэтому r _n - наибольший общий делитель чисел а и b.

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей (a, b). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что r _n = au + bv = (a, b).

Действительно, из цепочки равенств имеем:

r _n = r _{n -2} - r _{n -1} q _n = r _{n -2} - (r _{n -3} - r _{n -2} q _{n -1} ) q _n =...

(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)

... = au + bv = (a, b).

Пример. Пусть а = 525, b = 231. Отдадим эти числа на растерзание алгоритму Евклида: (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)

Запись того же самого в виде цепочки равенств:

525 = 231 · 2 + 63
231 = 63 · 3 + 42
63 = 42 · 1 + 21
42 = 21 · 2

Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя:

21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 =
= 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) =
= 525 · 4 - 231 · 9,

и наши пресловутые u и v из Z равны, соответственно, 4 и - 9.

Пункт 4 закончен.

Задачки

1. Предлагаю читателям самим придумать два разных трехзначных числа а и b и, непрерывно гундя и пикая металлическим голосом фразу: "Я исполнитель алгоритма Евклида", найти их наибольший общий делитель d и его представление в виде d = au + bv, u,v Î Z. Наиболее упорные могут усложнить себе задачу, заменив трехзначные числа четырехзначными, или даже пятизначными. Шестизначные числа брать не стоит, так как ваши родственники могут уже начать беспокоиться. 2. К великому беспокойству родственников, все-таки найдите d = (317811, 196418) и его представление в виде d = 317811 u + 196418 v. (1) 3. Найдите d = (81719, 52003, 33649, 30107).

(1) Числа 196418 и 317811 являются, соответственно, 27-ым и 28-ым членами последовательности Фибоначчи, с которой мы еще встретимся в этой книжке при анализе алгоритма Евклида. Для обработки алгоритмом Евклида этих двух чисел придется выполнить 26 делений с остатком, что, конечно, многовато для ручной работы, но я все-таки рекомендую вам ее проделать, дабы посмотреть, какие получаются остатки, и почему они получаются именно такими.