Kuṭṭaka - это алгоритм поиска целочисленных решений линейных диофантовых уравнений . Линейное диофантово уравнение - это уравнение вида ax + by = c, где x и y - неизвестные величины, а a , b и c - известные величины с целыми значениями. Алгоритм был первоначально изобретен индийским астрономом-математиком Арьябхана (476–550 гг. Н. Э.) И очень кратко описан в его книге «Арьябхатия».. Арьябхана не называл алгоритм именем Кунака , и его описание метода было в основном неясным и непонятным. Это был Бхаскара I (ок. 600 - ок. 680), который дал подробное описание алгоритма с несколькими примерами из астрономии в своей Арьябхатиябхашье , который дал алгоритму имя Кунака . На санскрите слово Kuṭṭaka означает измельчение ( превращение в порошок), и это указывает на природу алгоритма. По сути, алгоритм представляет собой процесс, в котором коэффициенты в данном линейном диофантовом уравнении разбиваются на меньшие числа, чтобы получить линейное диофантово уравнение с меньшими коэффициентами. В общем, легко найти целочисленные решения линейных диофантовых уравнений с малыми коэффициентами. Из решения редуцированного уравнения можно найти решение исходного уравнения. Многие индийские математики после Арьябханы обсуждали метод Кунаки с вариациями и уточнениями. Метод Kuaka считался настолько важным, что весь предмет алгебры раньше назывался Kuaka-ganita или просто Kuaka . Иногда объект решения линейных диофантовых уравнений также называют Kuṭṭaka .
В литературе есть несколько других названий алгоритма Kuaka , например Kua , Kuakāra и Kuikāra . Существует также трактат, посвященный исключительно обсуждению Кудака. Такие специализированные трактаты очень редко встречаются в математической литературе Древней Индии. [1] Трактат, написанный на санскрите, называется Kuṭṭākāra irmai, и его автором является некий Девараджа. [2]
Алгоритм Kuṭṭaka имеет много общего с современным расширенным алгоритмом Евклида и может считаться его предшественником . Последний алгоритм представляет собой процедуру нахождения целых чисел x и y, удовлетворяющих условию ax + by = gcd ( a , b ). [3]
Формулировка проблемы Арьябхатой
Проблема, которая предположительно может быть решена методом Кунаки, не была сформулирована Арьябхатой как проблема решения линейного диофантова уравнения. Арьябхана рассмотрел следующие задачи, все из которых эквивалентны задаче решения линейного диофантова уравнения:
- Найдите целое число, которое при делении на два заданных числа дает два заданных остатка . Эту проблему можно сформулировать двумя разными способами:
- Пусть найденное целое число равно N , делители равны a и b , а остатки равны R 1 и R 2 . Тогда проблема состоит в том, чтобы найти N такое, что
- N ≡ R 1 ( по модулю ) и N ≡ R 2 ( по модулю б ).
- Если найти целое число, равное N , делители равны a и b , а остатки равны R 1 и R 2 , задача состоит в том, чтобы найти N такое, что существуют такие целые числа x и y , что
- N = ax + R 1 и N = by + R 2 .
- Это эквивалентно
- ax - by = c, где c = R 2 - R 1 .
- Найдите такое целое число, чтобы его произведение с данным целым числом увеличивалось или уменьшалось на другое заданное целое число, а затем делилось на третье целое число, не оставляло остатка . Если определить целое число как x, а три целых числа - это a , b и c , задача состоит в том, чтобы найти x такое, что ( ax ± b ) / c является целым числом y . Это эквивалентно нахождению таких целых чисел x и y , что
- ( ах ± Ь ) / с = у .
- Это, в свою очередь, эквивалентно задаче нахождения целочисленных решений ax ± by = ± c .
Уменьшение проблемы
Арьябхат и другие индийские авторы были отмечены следующим свойством линейных диофантовых уравнений: «Линейное уравнение диофантов ах + с = с имеет решение тогда и только тогда , когда НОД ( , б ) является делителем из с .» Итак, первая стадия процесса измельчения состоит в том, чтобы исключить общий множитель gcd ( a , b ) из a , b и c и получить уравнение с меньшими коэффициентами, в котором коэффициенты при x и y являются взаимно простыми .
Например, Бхаскара 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 3 ---- Разделите 3 на 1, чтобы получить частное 3 и остаток 0: 1) 3 (3 1 ---- На этом процесс взаимного разделения останавливается. 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 ↗ к: 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 из Bhāskara I [4], показывает, как алгоритм Куттака использовался в астрономических расчетах в Индии. [5]
Постановка задачи
Сумма, разность и произведение, умноженное на единицу, остатков оборотов Сатурна и Марса - каждый представляет собой идеальный квадрат. Взяв уравнения, представленные выше, и применяя методы таких квадратичных, получим (простейшее) решение путем последовательной замены 2, 3 и т. Д. (В общем решении). Затем вычислите ахаргану и количество оборотов, совершенных Сатурном и Марсом за это время, а также количество прошедших солнечных лет.
Некоторая справочная информация
В индийской астрономической традиции юга - это период, состоящий из 1 577 917 500 гражданских дней. Сатурн совершает 146 564 оборота, а Марс - 229 6824 оборота за югу. Таким образом, Сатурн совершает 146,564 / 1,577,917,500 = 36,641 / 394,479,375 оборотов в день. Говоря, что остаток вращения Сатурна равен x , имеется в виду, что дробное число оборотов равно x / 394 479 375. Точно так же Марс совершает 229,6824 / 1,577,917,500 = 190,412 / 131,493,125 оборотов в день. Говоря, что остаток вращения Марса равен y , имеется в виду, что дробное число оборотов равно y / 131 493 125.
Расчет остатков
Пусть x и y обозначают остатки оборотов Сатурна и Марса соответственно, удовлетворяющие условиям, сформулированным в задаче. Они должны быть такими, чтобы каждый из x + y . x - y и xy + 1 - это полный квадрат.
Параметр
- х + у = 4 п 2 , х - у = 4 q 2
можно получить
- х = 2 ( р 2 + q 2 ) , у = 2 ( р 2 - q 2 )
и другие
- ху + 1 знак равно (2 п 2 - 1) 2 + 4 ( п 2 - q 4 ) .
Чтобы xy + 1 также был полным квадратом, мы должны иметь
- p 2 - q 4 = 0 , то есть p 2 = q 4 .
Таким образом получается следующее общее решение:
- х = 2 ( д 4 + д 2 ) , у = 2 ( д 4 - д 2 ) .
Значение q = 2 дает специальное решение x = 40, y = 24.
Вычисления ахарган и числа оборотов
Ахаргана - это количество дней, прошедших с начала Юги.
Сатурн
Пусть u будет значением ахарганы, соответствующим остатку 24 для Сатурна. За u дней сатурн совершил бы (36 641/394 479 375) × u число оборотов. Поскольку имеется остаток 24, это число также будет включать дробное число 24/394 479 375 оборотов. Следовательно, во время ахарганы u количество завершенных оборотов будет равно
- (36,641 / 394,479,375) × u - 24 / 394,479,375 = (36,641 × u - 24) / 394,479,375
что было бы целым числом. Обозначив это целое число через v , задача сводится к решению следующего линейного диофантова уравнения:
- (36 641 × u - 24) / 394 479 375 = v .
Куттака может применяться для решения этого уравнения. Наименьшее решение -
- u = 346 688 814 и v = 32 202.
Марс
Пусть u будет значением ахарганы, соответствующим остатку 40 для Марса. За u дней Марс совершил бы (190 412/131 493 125) × u число оборотов. Поскольку имеется остаток 40, это число также будет включать дробное число 40/131 493 125 оборотов. Следовательно, во время ахарганы u количество завершенных оборотов будет равно
- (190 412/131 493 125) × u - 40/131 493 125 = (190 412 × u - 40) / 131 493 125
что было бы целым числом. Обозначив это целое число через v , задача сводится к решению следующего линейного диофантова уравнения:
- (190 412 × u - 40) / 131 493 125 = v .
Куттака может применяться для решения этого уравнения. Наименьшее решение -
- u = 118 076 020 и v = 171 872.
Рекомендации
- ^ а б в г д Бибхутибхушан Датта и Авадхеш Нараян Сингх (1962). История индуистской математики. Книга-первоисточник. Часть II . Издательский дом "Азия". п. 92.
- ^ Девараджа (1944). Куттакара Сиромани (на санскрите) . Анандашрама Пресс . Проверено 7 марта +2016 .
- ^ DE Knuth (1998). Искусство программирования Том 2 . Pearson Education India , 1998. стр. 342. ISBN. 9788177583359.
- ^ Бхаскарачарья-1 (Перевод К.С. Шуклы) (1963). Лагху-Бхскария . Университет Лакхнау. п. 99 . Проверено 7 марта +2016 .
- ^ Авинаш Сатхай. "Лучший алгоритм деления" (PDF) . Математический факультет Univ. Кентукки . Проверено 7 марта +2016 .
дальнейшее чтение
- Для сравнения индийских и китайских методов решения линейных диофантовых уравнений: AK Bag и К.С. Шен (1984). «Куттака и Цювишу» (PDF) . Индийский журнал истории науки . 19 (4): 397–405. Архивировано из оригинального (PDF) 5 июля 2015 года . Проверено 1 марта 2016 года .
- Для сравнения сложности алгоритма Арьябхата со сложностями алгоритма Евклида, китайской теоремы об остатках и алгоритма Гарнера: TRN Рао и Чун-Хуанг Ян (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 .