Куттака

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

В литературе существует несколько других названий алгоритма Куттаки, например Кутта , Куттакара и Куттикара . Существует также трактат, посвященный исключительно обсуждению Куттаки. Подобные специализированные трактаты очень редки в математической литературе древней Индии. Трактат, написанный на санскрите, называется «Куттакара Широмани» , и его автором является Девараджа.

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

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

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

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

• которое нужно найти, равно N , делители — и b , а остатки — R1 _a и R2 _{Пусть целое число ,} . Тогда задача состоит в том, чтобы найти N такое, что

N ≡ R ₁ (mod a ) и N ≡ R ₂ (mod b ).

• искомое целое число равно N , делители — a и b , а остатки — R1 _Если и R2 _такие , задача состоит в том, чтобы найти N такое, что существуют целые числа x и y , что

N знак равно топор + р ₁ и N = by + р ₂ .

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

топор - by знак равно c где c знак равно р ₂ - р ₁ .

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

( топор ± б )/ c знак равно y .

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

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

Арьябхата и другие индийские писатели отметили следующее свойство линейных диофантовых уравнений: «Линейное диофантово уравнение + by = c имеет решение тогда и только тогда, когда НОД( a , b ) является делителем c ax ». Итак, первый этап процесса распыления — исключить общий множитель НОД( a , b ) из a , b и c и получить уравнение с меньшими коэффициентами, в котором коэффициенты при x и y являются относительно простыми .

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

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

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

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

«Делите делитель, соответствующий большему остатку, на делитель, соответствующий меньшему остатку. Остаток (и делитель, соответствующий меньшему остатку) взаимно делятся (пока остаток не станет нулевым), последнее частное следует умножить на необязательное целое число, а затем прибавляется (в случае, если число частных взаимного деления четное) или вычитается (в случае, если число частных нечетное) на разницу остатков. (Поместите остальные частные взаимного деления последовательно одно под другим в столбце; под ними только что полученный результат, а под ним необязательное целое число.) Любое число ниже (то есть предпоследнее) умножается на число чуть выше него. и прибавляем его чуть ниже последнего числа (полученного таким образом неоднократно) на делитель, соответствующий меньшему остатку, затем умножаем остаток на делитель, соответствующий большему остатку, и прибавляем больший остаток (The. результатом будет) число, соответствующее двум делителям».

Некоторые комментарии уместны.

• Алгоритм выдает наименьшее положительное целое число, которое дает заданный остаток при делении на заданные числа.
• Валидность алгоритма можно установить, переведя процесс в современные математические обозначения.
• Последующие индийские математики, в том числе Брахмагупта (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.

Используя евклидово деление , выполните следующие рекурсивные шаги:

а ′ знак равно а ₁ б ′ + р ₁

б ′ знак равно а ₂ р ₁ + р ₂

р ₁ = а ₃ р ₂ + р ₃

…

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 ₁ и x = c’x ₂ .

Пример

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

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

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

Данные

     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 — это наименьшее целое число, при делении которого на 29 и 45 получаются остатки 15 и 19 соответственно.

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

Следующий пример взят из Лагубхаскарии Бхаскары I. иллюстрирует, как алгоритм Куттака использовался в астрономических расчетах в Индии.

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

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

Вычисление остатков

Обозначим через x и y остатки оборотов Сатурна и Марса соответственно, удовлетворяющие условиям, поставленным в задаче. Они должны быть такими, что каждый из x + y . x − y и xy + 1 — полный квадрат.

Параметр

х + у = 4п ² , х - у знак равно 4 q ²

получается

х = 2( р ² + д ² ) , y = 2( п ² − q ² )

и так

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

Чтобы xy + 1 также было идеальным квадратом, мы должны иметь

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

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

х = 2( q ⁴ + д ² ) , y = 2( q ⁴ − q ² ) .

Значение q = 2 дает особое решение x = 40, y = 24.

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

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

Сатурн

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

(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 .

Для решения этого уравнения можно применить Куттаку. Самое маленькое решение

и = 346 688 814 и v = 32 202.

Марс

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

(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 .

Для решения этого уравнения можно применить Куттаку. Самое маленькое решение

и = 118 076 020 и v = 171 872.

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

• Для сравнения индийских и китайских методов решения линейных диофантовых уравнений: А. К. Баг и К. С. Шен (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 г. {{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка )