Kuaka

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

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

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

• 1 Формулировка проблемы Арьябхатой
• 2 Редукция проблемы
• 3 Алгоритм Арьябхаты
• 4 Пример
  • 4.1 Постановка задачи
  • 4.2 Данные
  • 4.3 Шаг 1: Взаимное деление
  • 4.4 Шаг 2: Выбор необязательного целого числа
  • 4.5 Шаг 4: Вычисление последовательных чисел
  • 4.6 Шаг 5: Вычисление решения
  • 4.7 Решение
  • 4.8 Проверка решения
  • 4.9 Замечания
• 5 Пример из Laghubhāskarīya
  • 5.1 Формулировка проблемы
  • 5.2 Некоторая справочная информация
  • 5.3 Вычисление остатков
  • 5.4 Вычисление ахарган и числа оборотов
    • 5.4.1 Сатурн
    • 5.4.2 Марс
• 6 Ссылки
• 7 Дополнительная литература

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

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

• Пусть целое число, которое нужно найти, равно N, делители - a и b, а остатки - R 1 и R 2. Тогда задача состоит в том, чтобы найти N такое, что

N ≡ R 1 (mod a) и N ≡ R 2 (mod b).

• Допустим, что целое число будет найдено равное 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 ± b) / c = y.

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

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

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

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

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

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

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

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

Рассмотрим следующую задачу:

«Найдите такое целое число, которое оставит остаток 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 соответственно.

Следующий пример, взятый из Лагхубхаскарии из Бхаскара 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 - это полный квадрат.

При установке

x + y = 4p, x - y = 4q

получаем

x = 2 (p + q), y = 2 (p - q)

и поэтому

xy + 1 = (2p - 1) + 4 (p - q).

Для того, чтобы xy + 1 также был полным квадратом, мы должны иметь

p - q = 0, то есть p = q.

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

x = 2 (q + 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 оборотов. Следовательно, во время ахраганы 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.

• Для сравнения индийских и китайских методов решения линейных диофантовых уравнений: A. К. Баг и К. С. Шен (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 г.