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: derecha|miniaturadeimagen|250x250px| Descripción de Kuttaka dada por Aryabhata en Aryabhatiya
"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 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 . Hay dos alternativas: si c no es divisible por , entonces no hay soluciones enteras para esta ecuación; si sí lo es, habremos obtenido la nueva ecuación cuya solución es también solución de la original . De nuevo y sin pérdida de generalidad, podemos considerar a > b.
Utilizando la división euclidiana, seguimos estos pasos recursivos:
a' = a1 b' + r1 b' = a2 r1+ r2 r1 = a3r2 + r3' ... rn-2 = an rn−1 + 1. Donde rn = 1.
Ahora, definamos las cantidades xn+2, xn+1, xn ,... por inducción de la siguiente manera: Si n es impar, tome xn+2 = 0 y xn+1 = 1. Si n es par, tome xn+2 = 1 y xn+1 = rn−1 − 1 y después calculemos todos los xm (n ≥ m ≥1) como x m = amxm+1 + xm+2 y entonces y = c' x1 y x=c' x2 .
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". Datos Restos = 15, 19 Resto mayor = 19 Divisor correspondiente al resto mayor = 45 Resto menor = 15 Divisor correspondiente al resto menor = 29 Diferencia de restos = 19 - 15 = 4
Dividir 45 por 29 para obtener cociente 1 y resto 16: 29 ) 45 ( 1 29
Dividir 29 por 16 para obtener cociente 1 y resto 13: 16 ) 29 ( 1 16
Dividir 16 por 13 para obtener cociente 1 y resto 3: 13 ) 16 ( 1 13
Dividir 13 por 3 para obtener cociente 4 y resto 1: 3 ) 13 ( 4 3
Dividir 3 por 1 para obtener el cociente 3 y el resto 0: 1 )3 (3 1
El proceso de división mutua termina aquí. 0
Cocientes = 1, 1, 1, 4, 3 Número de cocientes = 4 (un entero par) (excluyendo el primer cociente) Elija un entero opcional = 2 (= k) El último cociente = 3 Multiplica el entero opcional por el último cociente = 2 × 3 = 6 Sumar el producto anterior a la diferencia de residuos = 6 + 4 = 10 (= 3 × k + 4)
Paso 4: Cálculo de números sucesivos Escribe los elementos de la 1.ª columna : 1, 1, 4, 3, 2, 4 (contiene 4 cocientes) Calcular elementos de la 2.ª columna : 1, 1, 4, 10, 2 (contiene 3 cocientes) Calcular elementos de la 3.ª columna : 1, 1, 42, 10 (contiene 2 cocientes) Calcular elementos de la 4.ª columna : 1, 52, 42 (contiene 1 cociente) Calcular elementos de la 5.ª columna : 94, 52 (no contiene cocientes)
El procedimiento de cálculo se muestra a continuación:
Cociente 1 : 1 1 1 1 94 ↗ Cociente 2: 1 1 1 52 (52×1 + 42 = 94) 52 ↗ Cociente 3 : 4 4 42 (42×1 + 10 =52) 42 ↗ Cociente 4 : 3 10 (10×4 + 2 = 42) 10 ↗ k : 2 (2×3 + 4 = 10) 2
Diferencia: 4 de restos
Paso 5: Cálculo de la solución El último número obtenido = 94 El resto cuando 94 es dividido por el divisor correspondiente al resto menor = 7 Multiplicamos este residuo por el divisor correspondiente al resto mayor = 7 × 45 = 315 Sumamos el resto mayor = 315 + 19 = 334
Solución El número requerido es 334.' Verificación de la solución 334 = 11 × 29 + 15. Entonces, 334 deja un resto de 15 cuando se divide por 29. 334 = 7 × 45 + 19. Entonces, 334 deja un resto de 19 cuando se divide por 45. 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 , y sean todos cuadrados perfectos.
Configuración
,
uno obtiene
,
y entonces
.
Para que xy + 1 también sea un cuadrado perfecto debemos tener
, that is .
De esta forma se obtiene la siguiente solución general:
, .
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