Глава 5. Теория чисел в Азии

5.25. Евклидов алгоритм

Из предыдущих глав ясно, что древняя Греция оказала огромное влияние на мировую математику, и что большую часть фундаментальных понятий математики можно найти там. Это не означает, однако, что греки все открыли первыми, или, что они все делали лучше. Мы уже видели, что теорема Пифагора была известна в Вавилоне раньше, чем в Греции, и что пифагоровы тройки понимались там лучше, чем где-либо в Греции, по крайней мере, до времени Диофанта.

Действительно, теорема Пифагора и пифагоровы тройки также были известны в древнем Китае и Индии. Насколько нам известно, это были независимые открытия, поэтому скорее представляется, что теорема Пифагора — математически универсальна, вероятно, она появляется в любой достаточно развитой цивилизации. Другими такими универсалиями являются понятие отношение радиуса к окружности круга, и евклидов алгоритм. Как мы увидим в этой главе, евклидов алгоритм, по-видимому, появляется всякий раз, когда есть интерес к кратным, делителям и целочисленным решениям линейных и квадратных уравнений.

Для Евклида существовало два совершенно отдельных применения евклидова алгоритма. Во-первых, алгоритм применялся к целым числам и использовался, чтобы выводить заключения о делимости и простых числах. Во-вторых, алгоритм применялся к отрезвим прямых и использовался в качестве критерия иррациональности: если алгоритм не завершается, тогда отношение отрезков иррационально. Как мы видели в разделе 3.4, возможно, что греки продвинули евклидов алгоритм достаточно далеко, чтобы увидеть, что в некоторых случаях он становится периодическим; например, когда оба отрезви прямой имеют длины

Независимо от всех этих разработок, первая форма евклидова алгоритма появилась в Китае при Ханьской династии, между 200 г. до

н. э. и 200 г. н. э. Он использовался китайцами для упрощения дробей — деления числителя и знаменателя на их а также для отыскания решений линейных уравнений в целых числах.

Типичное «применение» такого уравнения следующее. Предположим, что в году дней и в лунном месяце 29 дней. Если мы переходим к единицам 1/4 дня, то год и лунный месяц тогда измеряются целыми числами 1461 и 118. Теперь предположим, что в первый день года полная луна. Сколько пройдет времени, прежде чем полная луна будет во второй день года? Это случится через х лет (и у месяцев), где

Мы, поэтому, ищем наименьшее целочисленное решение этого уравнения и, как мы видели в разделе 3.3, это зависит от выражения как комбинации вида I I Ну что может быть сделано с помощью евклидова алгоритма. В этом уравнении, конечно, нас лишь интересует часть решения, число х, потому что мы хотим знать лишь кратное 1461, которое в 4 меньше, чем некоторое кратное 118 (нам все равно, какое). Такую задачу позже описали бы как задачу о конгруэнтности: мы ищем х, так что 1461ж конгруэнтно Китайцы стали весьма искусны в таких задачах, расширив свои методы до множественной конгруэнтности, как объясняется в следующем разделе. Это привело к важной теореме, известной сегодня как китайская теорема об остатках.

Около пятого и шестого веков нашей эры, похожие линейные диофантовы уравнения решались в Индии, и, возможно, имелись в виду похожие проблемы календаря. Однако, индийцы приняли идею в ином направлении. Они независимо открыли уравнение Пелля найденное греками, пытавшимися понять а также вновь открыли в нем периодичность. Что примечательнее всего, они сделали это без такого-либо разбиения рационального и иррационального. Их трактовка уравнения Пелля полностью основывалась на целочисленных операциях, и она слегка сочетается с их трактовкой линейных уравнений.