Ариабхата: алгоритм куттака

Автор, датировавший себя сам

Ариабхата (476 — ок. 550) написал «Ариабхатию» — 121 стих предельно сжатого содержания: арифметика, алгебра, тригонометрия, астрономия. Стихотворная форма не украшение, а способ хранения: текст заучивался наизусть, а комментарии передавали смысл.

Датировка — редкая для древности роскошь, потому что автор указал её сам:

Когда прошло шестьдесят раз по шестьдесят лет и три четверти юги, мне было двадцать три года от рождения.

$60\cdot60=3600$ лет эры Калиюги дают 499 год, а возраст автора — 23. Место — Кусумапура, «город цветов», нынешняя Патна, тогда столица империи Гуптов.

Из прочего, что стоит знать об этой книге: приближение

$$\pi\approx\frac{62832}{20000}=3{,}1416,$$

причём Ариабхата добавляет слово asanna — «приближённо», редкий для эпохи признак понимания, что точного значения тут нет; таблица разностей синусов с шагом $3^\circ45'$ (и само слово «синус» произошло от индийского джья через арабское искажение джайб и латинское sinus); и утверждение, что Земля вращается вокруг оси, а видимое движение неба — следствие этого.

Куттака

Задача, ради которой изобретён метод, астрономическая: планеты имеют разные периоды, и требуется найти, через сколько дней данная конфигурация повторится. Математически это

$$ax\equiv c\pmod b,\qquad\text{то есть}\qquad ax+by=c\quad\text{в целых числах}.$$

Метод называется куттака (कुट्टक) — «измельчитель», «дробитель»: коэффициенты последовательно измельчаются, пока задача не станет тривиальной.

Как он работает. Уравнение $ax+by=c$ разрешимо тогда и только тогда, когда $\gcd(a,b)$ делит $c$. Прогоняем алгоритм ЕвклидаЕвклидгреческий математик · около 300 года до н. э.Автор книги, которая две тысячи лет была вторым по тиражу текстом после Библии, — и о котором самом не известно почти ничего. для $a$ и $b$, а затем идём по цепочке частных обратно, выражая остатки через исходные числа. По существу это то, что сегодня называют расширенным алгоритмом Евклида.

Пример. Решим $137x+56y=1$.

Прямой ход:

$$137=2\cdot56+25,\qquad 56=2\cdot25+6,\qquad 25=4\cdot6+1,\qquad 6=6\cdot1 .$$

Обратный ход:

$$1=25-4\cdot6=25-4(56-2\cdot25)=9\cdot25-4\cdot56=9(137-2\cdot56)-4\cdot56=9\cdot137-22\cdot56 .$$

Значит $x=9$, $y=-22$; общее решение $x=9+56t$, $y=-22-137t$. Проверка: $137\cdot9-56\cdot22=1233-1232=1$. $\checkmark$

Это ровно то вычисление, которое сегодня делает всякая программа, вычисляющая обратный элемент по модулю, — то есть каждый раз, когда генерируется ключ RSA.

Куда пошла эта линия

Индийская традиция после Ариабхаты — одна из самых сильных в истории теории чисел, и стоит проследить её до конца.

БрахмагуптаБрахмагуптаиндийский математик и астроном · 598 — около 668Первым в мире записал правила действий с нулём и отрицательными числами — как с законными числами, а не как с недоразумением; ошибся только в делении на нуль, и ошибку эту исправляли тысячу лет. (628) в «Брахмаспхутасиддханте» вводит правила действий с нулём и отрицательными числами (отдельная точка в линии алгебры) и берётся за уравнение

$$x^{2}-Ny^{2}=1$$

— то, что Европа по недоразумению назовёт уравнением Пелля. (Джон Пелль к нему отношения не имел вовсе: ЭйлерЛеонард Эйлершвейцарский математик, работавший в Петербурге и Берлине · 1707–1783Самый плодовитый математик в истории: около 900 работ, половина языка современной математики — от знака $\pi$ до записи $f(x)$ — и способность считать, не глядя. приписал ему чужую работу, и имя закрепилось — образцовый случай закона Стиглера.) Брахмагупта находит тождество композиции (бхавана):

$$(x_1^{2}-Ny_1^{2})(x_2^{2}-Ny_2^{2})=(x_1x_2+Ny_1y_2)^{2}-N(x_1y_2+x_2y_1)^{2},$$

позволяющее из двух решений строить третье. Проверить его можно прямым раскрытием скобок; по существу это утверждение о мультипликативности нормы в кольце $\mathbb{Z}[\sqrt N]$ — алгебраическая теория чисел за тысячу двести лет до её появления.

Джаядева (XI в.) и Бхаскара II (1150) доводят дело до чакравалы — циклического метода, всегда дающего наименьшее решение за конечное число шагов.

И вот кульминация сюжета. В 1657 году ФермаПьер Фермафранцузский юрист и математик · 1607–1665Советник тулузского парламента, не напечатавший при жизни ни одной математической книги — и успевший заложить теорию чисел, аналитическую геометрию, метод касательных и теорию вероятностей. посылает английским математикам вызов: решить $x^{2}-61y^{2}=1$. Число 61 выбрано не случайно — оно даёт устрашающий ответ:

$$x=1\,766\,319\,049,\qquad y=226\,153\,980 .$$

Броункер и ВаллисДжон Валлисанглийский математик и криптограф · 1616–1703Ввёл знак ∞, вычислил π бесконечным произведением и дал Ньютону приём, из которого тот сделал бином и ряды. справились, но с трудом и без доказательства, что метод всегда работает; полное обоснование дал ЛагранжЖозеф Луи Лагранжфранцузский математик и механик итальянского происхождения · 1736–1813Написал механику без единого чертежа, довёл до конца всё, что начали Эйлер и Ферма, и первым понял, что решаемость уравнения зависит от перестановок его корней. в 1768–1770 годах. А Бхаскара решил ровно этот пример методом чакравала в 1150 году — за пятьсот лет до вызова Ферма. Европа об этом не знала.

Задача. Найдите наименьшее решение уравнения $x^{2}-2y^{2}=1$ в натуральных числах и получите из него следующее по тождеству Брахмагупты.
(Ответ: $(3,2)$: $9-8=1$. Композиция решения с самим собой: $x'=3\cdot3+2\cdot2\cdot2=17$, $y'=3\cdot2+2\cdot3=12$; проверка $289-2\cdot144=289-288=1$. Заодно заметьте, что $17/12$ — хорошее приближение к $\sqrt2$, а $3/2$ — грубое: решения уравнения Пелля суть подходящие дроби цепной дроби корня.)

Следующая точка: Каир — где сформулируют критерий простоты, которого Европа будет ждать семь веков.