Индия · глава «Ганита», стих 32–33
Размельчитель
Условие
Найти наименьшее натуральное число, дающее остаток 5 при делении на 8, остаток 4 при делении на 9 и остаток 1 при делении на 7.
Показать ответ
85 (и вообще $85+504k$)
О чём эта задача
Ариабхата решает такие задачи алгоритмом, который назвал куттака, то есть размельчитель: цепочка делений с остатком, разматываемая обратно. Это алгоритм Евклида, применённый не для поиска общего делителя, а для решения уравнения в целых числах, — то, что мы зовём расширенным алгоритмом Евклида. Индийцам он был нужен для астрономии: чтобы узнать, через сколько дней два светила с разными периодами снова сойдутся.
Разбор — «как решали тогда» и «как решают сейчас» — для этой задачи ещё не написан.