Kuṭṭaka - Kuṭṭaka

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

В литературе есть несколько других названий алгоритма Kuaka , например Kua , Kuakāra и Kuikāra . Существует также трактат, посвященный исключительно обсуждению Кудака. Такие специализированные трактаты очень редко встречаются в математической литературе Древней Индии. Трактат, написанный на санскрите, называется Kuṭṭākāra irmai, его автором является некий Девараджа.

Алгоритм Kuṭṭaka имеет много общего и может рассматриваться как предшественник современного расширенного алгоритма Евклида . Последний алгоритм представляет собой процедуру нахождения целых чисел x и y, удовлетворяющих условию ax + by = gcd ( a , b ).

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

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

  • Найдите целое число, которое при делении на два заданных числа дает два заданных остатка . Эту проблему можно сформулировать двумя разными способами:
  • Пусть найденное целое число равно 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 замечает: «Дивиденд и делитель должны стать простыми по отношению друг к другу, будучи разделенными на остаток их взаимного деления. Работа измельчителя должна рассматриваться в отношении них».

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

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

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

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

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

Разработка Куттаки Арьябхатты

Без ограничения общности, пусть ax-by = c будет нашим диофантовым уравнением, где a , b - положительные целые числа, а c - целое число. Разделите обе части уравнения на gcd (a, b) . Если c не делится на gcd (a, b), то у этого уравнения нет целочисленных решений. После деления получаем уравнение a'x-b'y = c ' . Решением этого уравнения является решение ax-by = c . Без ограничения общности рассмотрим a> b.

Используя евклидово деление , выполните следующие рекурсивные шаги:
a '= a 1 b' + r 1
b '= a 2 r 1 + r 2
r 1 = a 3 r 2 + r 3
…
r n-2 = a n r n- 1 + 1 . Где r n = 1 .

Теперь определим величины x x + 2 , x n + 1 , x n , .. обратной индукцией следующим образом:
если n нечетное, возьмем x n + 2 = 0 и x n + 1 = 1.
 Если n четное, возьмем x n + 2 = 1 и x n + 1 = r n-1 -1 .
Теперь вычислим все x m (n≥m≥1) по x m = a m x m + 1 + x m + 2 . Тогда y = c'x 1 и x = c'x 2 .

Пример

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

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

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

Данные

     Remainders                                  = 15, 19
     Greater remainder                           = 19
     Divisor corresponding to greater remainder  = 45
     Smaller remainder                           = 15
     Divisor corresponding to smaller remainder  = 29
     Difference of remainders                    = 19 - 15 = 4

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

    Divide 45 by 29 to get quotient 1 and remainder 16: 29 ) 45 ( 1                       
                                                             29
                                                            ----
    Divide 29 by 16 to get quotient 1 and remainder 13:      16 ) 29 ( 1                  
                                                                  16
                                                                 ----
    Divide 16 by 13 to get quotient 1 and remainder  3:           13 ) 16 ( 1             
                                                                       13
                                                                      ----
    Divide 13 by  3 to get quotient 4 and remainder  1:                 3 ) 13 ( 4        
                                                                            3
                                                                           ----
    Divide  3 by  1 to get quotient 3 and remainder  0:                      1 )  3 ( 3   
                                                                                  1
                                                                                ----
    The process of mutual division stops here.                                    0

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

     Quotients                                         = 1, 1, 1, 4, 3
     Number of quotients                               = 4              (an even integer)
     (excluding the first quotient)
     Choose an optional integer                        = 2              (= k)
     The last quotient                                 = 3
     Multiply the optional integer by last quotient    = 2 × 3 =  6
     Add the above product to difference of remainders = 6 + 4 = 10     (= 3 × k + 4)

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

     Write elements of 1st column    :   1,  1,  4,  3, 2, 4 (contains 4 quotients)
     Compute elements of 2nd column  :   1,  1,  4, 10, 2    (contains 3 quotients)
     Compute elements of 3rd column  :   1,  1, 42, 10       (contains 2 quotients)
     Compute elements of 4th column  :   1, 52, 42           (contains 1 quotient)
     Compute elements of 5th column  :  94, 52               (contains no quotients)
     
     The computational procedure is shown below:
     
     Quotient 1   : 1                    1                      1                     1                      94  
                                                                                                           ↗
     Quotient 2   : 1                    1                      1                    52  (52×1 + 42 =  94)   52 
                                                                                   ↗ 
     Quotient 3   : 4                    4                     42  (42×1 + 10 =52)   42
                                                             ↗ 
     Quotient 4   : 3                   10   (10×4 + 2 = 42)   10 
                                      ↗
              k   : 2  (2×3 + 4 = 10)    2
     
     Difference   : 4
     of remainders

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

     The last number obtained                                                           = 94
     The residue when 94 is divided by the divisor corresponding to smaller remainder   = 7 
     Multiply this residue by the divisor corresponding to larger remainder             = 7 × 45 = 315
     Add the larger remainder                                                           = 315 + 19 = 334

Решение

Требуемый номер - 334.

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

     334 = 11 × 29 + 15. So, 334 leaves a remainder of 15 when divided by 29.
     334 =  7 × 45 + 19. So, 334 leaves a remainder of 19 when divided by 45.

Замечания

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

Пример из Лагхубхаскарии

Следующий пример, взятый из Laghubhāskarīya из Bhāskara I, показывает, как алгоритм Куттака использовался в астрономических расчетах в Индии.

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

Сумма, разность и произведение, умноженное на единицу, остатков оборотов Сатурна и Марса - каждый представляет собой идеальный квадрат. Взяв уравнения, представленные выше, и применяя методы таких квадратичных, получаем (простейшее) решение путем последовательной замены 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.

использованная литература

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

  • Для сравнения индийских и китайских методов решения линейных диофантовых уравнений: А. К. Баг и К. С. Шен (1984). «Куттака и Цювишу» (PDF) . Индийский журнал истории науки . 19 (4): 397–405. Архивировано из оригинального (PDF) 5 июля 2015 года . Проверено 1 марта 2016 года .
  • Для сравнения сложности алгоритма Арьябхата со сложностями алгоритма Евклида, китайской теоремы об остатках и алгоритма Гарнера: TRN Rao and Chung-Huang Yang (2006). «Теорема об остатке Арьябхаты: актуальность для криптосистем с открытым ключом» (PDF) . Схемы, системы, обработка сигналов . 25 (1): 1–15 . Проверено 1 марта 2016 года .
  • Для популярного читаемого отчета о Куттаке: Amartya Kumar Dutta (октябрь 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 .