Kuṭṭaka - Kuṭṭaka

Kuṭṭaka является алгоритм для поиска целое число решения линейный Диофантовы уравнения. Линейное диофантово уравнение - это уравнение формы топор + к = c куда Икс и у находятся неизвестные количества и а, б, и c - известные величины с целыми значениями. Изначально алгоритм был изобретен индийским астрономом-математиком. Ryabhaa (476–550 гг. Н. Э.) И очень кратко описан в его Ryabhaīya. Арьябхана не дал алгоритму название Kuṭṭaka, и его описание метода было в основном неясным и непонятным. Это было Бхаскара I (ок. 600 - ок. 680), который дал подробное описание алгоритма с несколькими примерами из астрономии в своей Ryabhatiyabhāya, давший алгоритму имя Kuṭṭaka. В санскрит, слово Kuṭṭaka означает измельчение (превращаясь в порошок), и это указывает на природу алгоритма. По сути, алгоритм представляет собой процесс, в котором коэффициенты в данном линейном диофантовом уравнении разбиваются на меньшие числа, чтобы получить линейное диофантово уравнение с меньшими коэффициентами. В общем случае легко найти целочисленные решения линейных диофантовых уравнений с малыми коэффициентами. Из решения редуцированного уравнения может быть найдено решение исходного уравнения. Многие индийские математики после Арьябханы обсуждали метод Кунаки с вариациями и уточнениями. Метод Kuṭṭaka считался настолько важным, что весь предмет алгебры раньше назывался Kuaka-ganita или просто Kuṭṭaka. Иногда предмет решения линейных диофантовых уравнений также называют Kuṭṭaka.

В литературе есть несколько других названий алгоритма Kuṭṭaka, например Kuṭṭa, Kuṭṭakāra и Kuṭṭikāra. Существует также трактат, посвященный исключительно обсуждению Кудака. Такие специализированные трактаты очень редко встречаются в математической литературе Древней Индии.^[1] Трактат, написанный на санскрите, называется Kuṭṭākāra irmai и автором одного Девараджа.^[2]

Алгоритм Kuṭṭaka очень похож и может считаться предшественником наших дней. расширенный алгоритм Евклида. Последний алгоритм представляет собой процедуру нахождения целых чисел Икс и у удовлетворяющий условию топор + к = gcd (а, б).^[3]

Формулировка проблемы Арьябхатой

Проблема, которая предположительно может быть решена с помощью метода Кудака, не была сформулирована Арьябхатой как проблема решения линейного диофантова уравнения. Арьябхана рассмотрел следующие задачи, все из которых эквивалентны задаче решения линейного диофантова уравнения:

• Найдите целое число, которое при делении на два заданных числа оставляет два заданных остатка.. Эту проблему можно сформулировать двумя разными способами:

• Пусть найденное целое число равно N, делители будут а и б, а остальные будут р₁ и р₂. Тогда проблема в том, чтобы найти N такой, что

N ≡ р₁ (мод а) и N ≡ р₂ (мод б).

• Позволяя найти целое число N, делители будут а и б, а остальные будут р₁ и р₂, проблема в том, чтобы найти N такие, что есть целые числа Икс и у такой, что

N = топор + р₁ и N = к + р₂.

Это эквивалентно

топор − к = c куда c = р₂ − р₁.

• Найдите такое целое число, чтобы его произведение с данным целым числом увеличивалось или уменьшалось на другое данное целое число, а затем делилось на третье целое число, не оставляло остатка. Позволяя определить целое число Икс и три целых числа будут а, б и c, проблема в том, чтобы найти Икс такой, что (топор ± б)/c это целое число у. Это эквивалентно поиску целых чисел Икс и у такой, что

(топор ± б)/c = у.

Это, в свою очередь, эквивалентно задаче нахождения целочисленных решений топор ± к = ±c.

Уменьшение проблемы

Арьябхата и другие индийские писатели отметили следующее свойство линейных диофантовых уравнений: «Линейное диофантово уравнение топор + к = c имеет решение тогда и только тогда, когда gcd (а, б) это делитель из c. "Итак, первый этап в измельчение процесс заключается в сокращении общего множителя gcd (а, б) из а, б и c, и получим уравнение с меньшими коэффициентами, в котором коэффициенты при Икс и у находятся относительно простой.

Например, Бхаскара I замечает: «Дивиденд и делитель должны стать простыми по отношению друг к другу, будучи разделенными на остаток их взаимного деления. Работа измельчителя должна рассматриваться в отношении них».^[1]

Алгоритм Арьябхаты

Арьябхата дал алгоритм решения линейного диофантова уравнения в стихах 32–33 Ганитапады из Арьябхатии.^[1] Принимая во внимание объяснение этих стихов Бхаскарой I, Бибхутиббхушан Датта дал следующий перевод этих стихов:

Описание Куттаки, данное Арьябхатой в Арьябхатии

"Разделите делитель, соответствующий большему остатку, на делитель, соответствующий меньшему остатку. Остаток (и делитель, соответствующий меньшему остатку) делятся взаимно (пока остаток не станет равным нулю), последнее частное следует умножить на необязательное целое число, а затем складывается (в случае четного числа частных при взаимном делении) или вычитается (в случае нечетного числа частных) на разность остатков (поместите другие частные при взаимном делении последовательно на одну ниже другое в столбце; под ними - только что полученный результат, а под ним - необязательное целое число.) Любое число под ним (то есть предпоследнее) умножается на то, что находится чуть выше него, и добавляется к нему чуть ниже. Разделите последнее число ( полученный таким образом многократно) на делитель, соответствующий меньшему остатку; затем умножьте остаток на делитель, соответствующий большему остатку, и сложите больший остаток (результат будет l be) число, соответствующее двум делителям ".

Некоторые комментарии по порядку.

• Алгоритм дает наименьшее положительное целое число, которое дает указанные остатки при делении на заданные числа.
• Достоверность алгоритма может быть установлена ​​путем перевода процесса в современные математические представления.^[1]
• Последующие индийские математики, включая Брахмагупта (628 г. н.э.), Махавира (850), Арьябхата II (950), Шрипати (1039), Бхаскара II (1150) и Нараяна (1350) разработали несколько вариантов этого алгоритма, а также обсудили несколько частных случаев алгоритма.^[1]

Пример

Постановка задачи

Рассмотрим следующую проблему:

«Найдите такое целое число, которое оставит остаток 15 при делении на 29 и остаток 19 при делении на 45».

Данные

     Остаток = 15, 19 Большой остаток = 19 Делитель, соответствующий большему остатку = 45 Меньший остаток = 15 Делитель, соответствующий меньшему остатку = 29 Разница остатков = 19-15 = 4

Шаг 1: Взаимное разделение

    Разделите 45 на 29, чтобы получить частное 1 и остаток 16:29) 45 (1 29 ---- разделите 29 на 16, чтобы получить частное 1 и остаток 13:16) 29 (1 16 ---- Разделите 16 на 13, чтобы получить частное 1 и остаток 3:13) 16 (1 13 ---- Разделите 13 на 3, чтобы получить частное 4 и остаток 1: 3) 13 (4 12 ---- Разделите 3 на 1, чтобы получить частное 3 и остаток 0:1) 3 (3 3 ---- На этом процесс взаимного деления заканчивается. 0

Шаг 2. Выбор необязательного целого числа

     Частные = 1, 1, 1, 4, 3 Количество частных = 4 (четное целое число) (исключая первое частное) Выберите необязательное целое число = 2 (= k) Последнее частное = 3 Умножьте необязательное целое число на последнее частное = 2 × 3 = 6 Добавьте указанный выше продукт к разности остатков = 6 + 4 = 10 (= 3 × k + 4)

Шаг 4: Вычисление последовательных чисел

     Запишите элементы 1-го столбца: 1, 1, 4, 3, 2, 4 (содержит 4 частных) Вычислите элементы 2-го столбца: 1, 1, 4, 10, 2 (содержит 3 частных). Вычислите элементы 3-го столбца: 1, 1, 42, 10 (содержит 2 частных) Вычислить элементы 4-го столбца: 1, 52, 42 (содержит 1 частное) Вычислить элементы 5-го столбца: 94, 52 (не содержит частных) Вычислительная процедура показана ниже: Фактор 1: 1 1 1 1 94 ↗ Частное 2: 1 1 1 52 (52 × 1 + 42 = 94) 52 ↗ Фактическое 3: 4 4 42 (42 × 1 + 10 = 52) 42 ↗ Частное 4: 3 10 (10 × 4 + 2 = 42) 10 ↗ k: 2 (2 × 3 + 4 = 10) 2 Разница: 4 остатка

Шаг 5: Расчет решения

     Последнее полученное число = 94 Остаток при делении 94 на делитель, соответствующий меньшему остатку = 7 Умножьте этот остаток на делитель, соответствующий большему остатку = 7 × 45 = 315 Добавьте больший остаток = 315 + 19 = 334

Решение

Требуемое число - 334.

Проверка решения

     334 = 11 × 29 + 15. Итак, 334 оставляет остаток от 15 при делении на 29. 334 = 7 × 45 + 19. Итак, 334 оставляет остаток от 19 при делении на 45.

Замечания

Число 334 - это самый маленький целое число, которое оставляет остатки 15 и 19 при делении на 29 и 45 соответственно.

Пример из Laghubhāskarīya

Следующий пример взят из Laghubhāskarīya из Бхаскара I^[4] иллюстрирует, как алгоритм Куттака использовался в астрономических расчетах в Индии.^[5]

Постановка задачи

Сумма, разность и произведение, умноженное на единицу, остатков оборотов Сатурна и Марса - каждый представляет собой полный квадрат. Взяв уравнения, представленные выше, и применяя методы таких квадратичных, получим (простейшее) решение путем последовательной замены 2, 3 и т.д. (в общем решении). Затем рассчитайте Ахаргана и количество обращений, совершенных Сатурном и Марсом за это время, вместе с количеством прошедших солнечных лет.

Некоторая справочная информация

В индийской астрономической традиции Юга период, состоящий из 1 577 917 500 гражданских дней. Сатурн совершает 146 564 оборота, а Марс - 229 6824 оборота за югу. Таким образом, Сатурн совершает 146,564 / 1,577,917,500 = 36,641 / 394,479,375 оборотов в день. Говоря, что остаток вращения Сатурна Икс, имеется в виду, что дробное число оборотов равно Икс/ 394 479 375. Точно так же Марс совершает 229,6824 / 1,577,917,500 = 190,412 / 131,493,125 оборотов в день. Говоря, что остаток вращения Марса есть у, имеется в виду, что дробное число оборотов равно у/131,493,125.

Расчет остатков

Позволять Икс и у обозначают остатки оборотов Сатурна и Марса соответственно, удовлетворяющие условиям, сформулированным в задаче. Они должны быть такими, чтобы каждый из Икс + у. Икс − у и ху + 1 идеальный квадрат.

Параметр

Икс + у = 4п², Икс − у = 4q²

можно получить

Икс = 2(п² + q²), у = 2(п² − q²)

и так

ху + 1 = (2п² − 1)² + 4(п² − q⁴).

За ху +1 также, чтобы быть идеальным квадратом, мы должны иметь

п² − q⁴ = 0, то есть п² = q⁴.

Таким образом получается следующее общее решение:

Икс = 2(q⁴ + q²), у = 2(q⁴ − q²).

Значение q = 2 дает специальное решение Икс = 40, у = 24.

Расчеты Ахарганас и числа оборотов

Ахаргана это количество дней, прошедших с начала Юги.

Сатурн

Позволять ты - значение ахарганы, соответствующее остатку 24 для Сатурна. В течение ты дней, Сатурн завершил бы (36,641 / 394,479,375) ×ты количество оборотов. Поскольку остаток равен 24, это число также будет включать дробное число 24/394 479 375 оборотов. Следовательно, во время ахраганы ты, количество завершенных оборотов будет

(36,641 / 394,479,375) × ты − 24/394,479,375 = (36,641 × ты − 24) / 394,479,375

который был бы целым числом. Обозначая это целое число как v, задача сводится к решению следующего линейного диофантова уравнения:

(36,641 × ты − 24) / 394,479,375 = v.

Куттака может применяться для решения этого уравнения. Наименьшее решение -

ты = 346 688 814 и v = 32,202.

Марс

Позволять ты - значение ахарганы, соответствующее остатку 40 для Марса. В течение ты дней, Марс завершил бы (190 412/131 493 125) × ты количество оборотов. Поскольку имеется остаток 40, это число также будет включать дробное число 40/131 493 125 оборотов. Следовательно, во время ахраганы ты, количество завершенных оборотов будет

(190,412 / 131,493,125) × ты − 40 / 131,493,125 = (190,412 × ты − 40) / 131,493,125

которое будет целым числом. Обозначая это целое число как v, задача сводится к решению следующего линейного диофантова уравнения:

(190,412 × ты − 40) / 131,493,125 = v.

Куттака может применяться для решения этого уравнения. Наименьшее решение -

ты = 118 076 020 и v = 171,872.

Рекомендации

дальнейшее чтение

• Для сравнения индийских и китайских методов решения линейных диофантовых уравнений: А. К. Баг и К. С. Шен (1984). «Куттака и Цювишу» (PDF). Индийский журнал истории науки. 19 (4): 397–405. Архивировано из оригинал (PDF) 5 июля 2015 г.. Получено 1 марта 2016.
• Для сравнения сложности алгоритма Арьябхата со сложностями алгоритма Евклида, китайской теоремы об остатках и алгоритма Гарнера: Т. Р. Н. Рао и Чун-Хуанг Ян (2006). «Теорема об остатке Арьябхаты: актуальность для криптосистем с открытым ключом» (PDF). Схемы, Система, Обработка сигналов. 25 (1): 1–15. Получено 1 марта 2016.
• Для популярного читаемого описания Куттаки: Амартья Кумар Дутта (октябрь 2002 г.). "Математика в Древней Индии 2. Диофантовы уравнения: Куттака" (PDF). Резонанс. 7 (10): 6–22. Получено 1 марта 2016.^{[постоянная мертвая ссылка ]}
• Для применения Куттаки в вычислении дней полнолуния: Роберт Кук. «Алгоритм Евклида» (PDF). Архивировано из оригинал (PDF) 15 июня 2016 г.. Получено 1 марта 2016.
• Для обсуждения вычислительных аспектов алгоритма Арьябхата: Субхаш Как (1986). «Вычислительные аспекты алгоритма Арьябхата» (PDF). Индийский журнал истории науки. 21 (1): 62–71. Получено 1 марта 2016.
• Для интерпретации оригинальной формулировки алгоритма Арьябхаты: Бибхутибхусан Датта (1932). «Правило старейшины Арьябхаты для решения неопределенных уравнений первой степени». Бюллетень математического общества Калькутты. 24 (1): 19–36.
• Для подробного изложения алгоритма Куттака, данного Шанкаранараяной в его комментарии к Лагубхаскарии: Бхаскарачарья-1 (Перевод К. С. Шуклы) (1963). Лагху-Бхскария. Университет Лакхнау. стр.103 –114. Получено 7 марта 2016.