Алгоритм Эвклида

Самым древним нетривиальным алгоритмом является способ нахождения наибольшего общего делителя двух целых чисел – алгоритм Эвклида. Он был изложен в трудах древнегреческого математика Эвклида – седьмой книге "Начал" – около 2300 лет тому назад. Конечно, можно возразить – а как же древние египтяне? Вавилоняне? Неужели они не смогли предложить более древний алгоритм? Вычисления древних египтян и вавилонян найдены, они старше греческих на полторы тысячи лет, но алгоритм Эвклида имеет одну существенную разницу – он является итерационным, то есть имеет неоднократное повторение определенных действий.

Алгоритм Эвклида имеет одну существенную разницу – он является итерационным, то есть имеет неоднократное повторение определенных действий

Рассмотрим сам алгоритм Эвклида нахождения наибольшего общего делителя двух целых положительных чисел. Вот как он реализуется.

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

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

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

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

Поскольку B делит С, которое, в свою очередь, делит А – Е, то B делит А – Е; B делит также все А, следовательно, оно делит и остаток Е. Но Е делит С – Е, поэтому B делит С – Е. Но B делит также все С, следовательно, оно делит и остаток F; таким образам, большее число делит меньшее, а это невозможно.

Поэтому нет такого числа, большего, чем F, которое делило бы числа А и С, и, значит, F – их наибольшии общий делитель.

В заключение хотелось бы сказать, что вавилонские и египетские алгоритмы представляют исключительно исторический интерес, в то время как алгоритм Эвклида не потерял своего практического значения до сих пор.

Инструменты