# Kuttaka

El algoritmo de Kuṭṭaka es un algoritmo para encontrar soluciones enteras de ecuaciones diofánticas lineales. Las ecuaciones diofánticas lineales son ecuaciones de la forma ax + by = c, donde x e y son las variables y a, b y c son valores enteros. Este algoritmo fue inventado originalmente por el astrónomo y matemático indio Āryabhaṭa (476–550 d. C.), que describe muy brevemente en su libro Āryabhaṭīya. Āryabhaṭa no le dio originalmente el nombre Kuṭṭaka y la descripción del algoritmo fue en su mayor parte poco clara e incomprensible. Fue Bhāskara I (c. 600 – c. 680) quien dio una descripción detallada del mismo con algunos ejemplos de astronomía en su obra Āryabhatiyabhāṣya y quien acuñó finalmente el nombre de Kuṭṭaka. En sánscrito, la palabra Kuṭṭaka significa pulverización y es un término representativo de la naturaleza del algoritmo. Este fundamentalmente consiste en dividir los coeficientes de la ecuación original en números más pequeños para obtener una reducida con coeficientes más sencillos porque, en general, encontrar soluciones enteras de ecuaciones diofánticas lineales con coeficientes pequeños es un problema de menor dificultad. Después, se puede determinar una solución de la ecuación original a partir de su solución para la ecuación reducida. Muchos matemáticos indios después de Aryabhaṭa han discutido el método Kuṭṭaka con variaciones y refinamientos. De hecho, el algoritmo de Kuṭṭaka se consideraba tan importante en su momento que todo el Álgebra solía llamarse Kuṭṭaka-ganita o Kuṭṭaka y resolver ecuaciones diofánticas lineales habitualmente también se denominaba Kuṭṭaka.
En la literatura matemática, se le dan varios nombres alternativos como Kuṭṭaka, Kuṭṭa, Kuṭṭakāra o Kuṭṭikāra. De la misma manera, hay un tratado dedicado exclusivamente a la discusión de Kuṭṭaka, lo que es algo inusual en la literatura matemática de la antigua India, pues no solía haber muchos manuales especializados.Este tratado, escrito en sánscrito, se titula Kuṭṭākāra Śirōmaṇi y su autor es Devaraja.
El algoritmo Kuṭṭaka tiene muchos puntos similares al algoritmo euclidiano extendido moderno y puede considerarse como un precursor de este. El algoritmo euclidiano extendido es procedimiento para encontrar números enteros x e y que satisfagan la condición ax + by = mcd ( a, b ).

## La formulación del problema de Aryabhaṭa.

El problema original para el que Aryabhaṭa diseñó el algoritmo no se corresponde a priori con un problema de solución de ecuaciones diofánticas lineales. Aryabhaṭa, en su momento, formuló los siguientes problemas que posteriormente se han demostrado equivalentes al mencionado:
* Encuentra un número entero que al dividirlo por dos números enteros dados deja dos residuos dados . Este problema puede formularse de dos maneras diferentes:
   * Sea N el número entero a encontrar, los divisores a y b, y los residuos R $_1$ y R $_{2,}$ entonces el problema consiste en encontrar un N tal que
          N ≡ R $_1$ (mod a ) y N ≡ R $_2$ (mod b ).
   * Sea N el número entero a encontrar, los divisores a y b, y los residuos R $_1$ y R $_2$, entonces el problema consiste en encontrar un N para el que existan enteros x e y tales que
          N = ax + R $_1$ y N = by + R $_2$ .
       Esto es equivalente a
          ax−by = c donde c = R $_2$ − R $_1$ $_.$
* Encuentra un número entero tal que su producto con otro dado incrementado o decrementado un segundo entero dado y después divido por un tercer entero no deje resto. Si el entero a determinar es x y los tres enteros a, b y c, el problema es encontrar x tal que ( ax ± b )/ c sea un entero y . Esto es equivalente a encontrar los enteros x e y tales que
       ( ax ± b )/ c = y .
    Lo que a su vez es equivalente a encontrar soluciones enteras de ax ± by = ± c.

## Reducción del problema

Aryabhata y otros escritores indios habían notado la siguiente propiedad de las ecuaciones diofánticas lineales: "La ecuación diofántica lineal ax + by = c tiene solución si y sólo si mcd(a, b) es un divisor de c ". Por tanto, la primera etapa en el proceso de pulverización es dividir ambos lados por el mcd(a, b) de a y b para obtener una ecuación con coeficientes más pequeños en la que los coeficientes de x e y sean coprimos .
Por ejemplo, Bhāskara I hizo la siguiente observación: “El dividendo y el divisor se volverán coprimos cuando se dividan por el resto de su división mutua. La operación del pulverizador debe considerarse en relación con ellos”.

## Algoritmo de Aryabhata

Aryabhata escribió el algoritmo que resuelve la ecuación diofántica lineal en los versos 32-33 de Ganitapada de Aryabhatiya. Haciendo uso también de la explicación de Bhāskara I con respecto al problema, Bibhutibbhushan Datta dio la siguiente traducción de estos versos:
    "Dividir el divisor correspondiente al resto mayor por el divisor correspondiente al resto menor. Divididos mutuamente el residuo (y el divisor correspondiente al resto menor) (hasta que el resto sea cero), el último cociente debe ser multiplicado por un entero opcional y luego sumado (en caso de que el número de cocientes de la división mutua sea par) o restado (en caso de que el número de cocientes sea impar) a la diferencia de los residuos. (Colocar los otros cocientes de la división mutua sucesivamente uno debajo del otro en una columna; debajo de ellos el resultado recién obtenido y debajo el entero opcional.) Cualquier número que esté debajo (es decir, el penúltimo) se multiplica por el inmediatamente superior y se suma por el inmediatamente inferior. Dividir el último número (obtenido así haciendo repetidamente) por el divisor correspondiente al resto menor; luego multiplicar el residuo por el divisor correspondiente al resto mayor y sumar el resto mayor. (El resultado será) el número correspondiente a los dos divisores."
Es conveniente hacer algunos comentarios.
* El algoritmo produce el número entero positivo más pequeño que da residuos específicos cuando se divide por números dados.
* La validez del algoritmo se puede establecer traduciendo el proceso a notaciones matemáticas modernas.
* Matemáticos indios posteriores, entre ellos Brahmagupta (628 d. C.), Mahavira (850), Aryabhata II (950), Sripati (1039), Bhāskara II (1150) y Narayana (1350), desarrollaron varias variantes de este algoritmo y también analizaron varios casos especiales del mismo.

## Elaboración de Aryabhatta's Kuttaka

Sin pérdida de generalidad, podemos suponer que ⁠$ax-by=c$⁠ es nuestra ecuación diofántica donde a, b son enteros positivos y c es un entero. Dividamos ambos lados de la ecuación por ⁠$\gcd(a,b)$⁠. Hay dos alternativas: si c no es divisible por ⁠$\gcd(a,b)$⁠, entonces no hay soluciones enteras para esta ecuación; si sí lo es, habremos obtenido la nueva ecuación ⁠$a'x-b'y=c'$⁠ cuya solución es también solución de la original ⁠$ax-by=c$⁠ . De nuevo y sin pérdida de generalidad, podemos considerar a > b.
Utilizando la división euclidiana, seguimos estos pasos recursivos:
    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. Donde r$_n$ = 1.
Ahora, definamos las cantidades x$_n$$_{+2}$, x$_{n+1}$, x$_n$ ,... por inducción de la siguiente manera: Si n es impar, tome x$_{n+2}$ = 0 y x$_{n+1}$ = 1. Si n es par, tome x$_{n+2}$ = 1 y x$_{n+1}$ = r$_{n−1}$ − 1 y después calculemos todos los x$_m$ (n ≥ m ≥1) como x $_m$ = a$_m$x$_{m+1}$ + x$_{m+2}$ y entonces y = c' x$_1$ y x=c' x$_2$ .

## Ejemplo
### Planteamiento del problema

Consideremos el siguiente problema:
    "Encuentra un número entero que deje un resto de 15 cuando se divida por 29 y un resto de 19 cuando se divida por 45".

### Solución

El número requerido es 334.

### Verificación de la solución

El número 334 es el entero más pequeño que deja como restos 15 y 19 cuando es dividido respectivamente por 29 y 45 .

## Un ejemplo de Laghubhāskarīya

El siguiente ejemplo sacado de Laghubhāskarīya of Bhāskara I ilustra como el algoritmo de Kuttaka se usaba en los cálculos astronómicos en la India.

### Planteamiento del problema

La suma, la diferencia y el producto aumentado una unidad de los restos de las revoluciones de Saturno y Marte son un cuadrado perfecto cada uno. Utilizando las ecuaciones previas y empleando los métodos de esas ecuaciones cuadráticas se obtiene la solución (más simple) mediante la sustitución de 2, 3, etc. sucesivamente (en la solución general). Luego, basta con calcular el ahargana y las revoluciones realizadas por Saturno y Marte en ese tiempo junto con el número de años solares transcurridos.

### Algunos antecedentes

En la tradición astronómica india, llamamos Yuga a un período que consta de 1.577.917.500 días civiles. En una Yuga, Saturno hace 146.564 revoluciones y Marte, 229.6824, luego Saturno realiza 146.564/1.577.917.500 = 36.641/394.479.375 revoluciones al día y Marte 229.6824/1.577.917.500 = 190.412/131.493.125. Cuando decimos que el resto de la revolución de Saturno es x y el de Marte es y, a lo que nos referimos en realidad es a que el número fraccional de revoluciones de cada uno es x /394.479.375 e y /131.493.125 respectivamente.

### Cálculo de los residuos

Sean x e y los residuos de las revoluciones de Saturno y Marte respectivamente que satisfacen las condiciones establecidas en el problema, ambos deben verificar que x + y, x − y y xy + 1 sean todos cuadrados perfectos.
Configuración
    x + y = 4p$^2$, x − y = 4q$^2$
uno obtiene
    x = 2(p$^2$ + q$^2$), y = 2(p$^2$ − q$^2$)
y entonces
    xy + 1 = (2p$^2$ − 1)$^2$ + 4(p$^2$ − q$^4$).
Para que xy + 1 también sea un cuadrado perfecto debemos tener
    p$^2$ − q$^4$ = 0, that is p$^2$ = q$^4$.
De esta forma se obtiene la siguiente solución general:
    x = 2(q$^4$ + q$^2$), y = 2(q$^4$ − q$^2$).
El valor q = 2 produce la solución especial x = 40, y = 24.

### Cálculos de los aharganas y el número de revoluciones

Ahargana es el número de días transcurridos desde el comienzo del Yuga.

#### Saturno

Sea u el valor del ahargana correspondiente al residuo 24 de Saturno. Durante u días, Saturno habría completado (36.641/394.479.375)× u número de revoluciones. Como hay un residuo de 24, este número incluiría también el número fraccionario 24/394.479.375 de revoluciones. Por lo tanto, durante el ahargana u, el número de revoluciones completadas sería
    (36,641 / 394,479,375) × u − 24/394,479,375 = (36,641 × u − 24) / 394,479,375
que sería un número entero. Denotando este entero por v, el problema se reduce a resolver la siguiente ecuación diofántica lineal:
    (36,641 × u − 24) / 394,479,375 = v.
Se puede aplicar Kuttaka para resolver esta ecuación. La solución más pequeña es
    u = 346.688.814 y v = 32.202.

#### Marte

Sea u el valor del ahargana correspondiente al resto 40 para Marte. Durante u días, Marte habría completado (190.412/131.493.125) × u número de revoluciones. Como hay un residuo de 40, este número también incluiría el número fraccionario 40/131.493.125 de revoluciones. Por lo tanto, durante el ahargana u, el número de revoluciones completadas sería
    (190,412 / 131,493,125) × u − 40 / 131,493,125 = (190,412 × u − 40) / 131,493,125
que sería un número entero. Denotando este entero por v, el problema se reduce a resolver la siguiente ecuación diofántica lineal:
    (190,412 × u − 40) / 131,493,125 = v.
Se puede aplicar Kuttaka para resolver esta ecuación. La solución más pequeña es
    u = 118.076.020 y v = 171.872.