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.^[1]​Este tratado, escrito en sánscrito, se titula Kuṭṭākāra Śirōmaṇi y su autor es Devaraja. ^[2]​

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 ). ^[3]​

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 ₁ y R _2, entonces el problema consiste en encontrar un N tal que

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

• Sea N el número entero a encontrar, los divisores a y b, y los residuos R ₁ y R ₂, entonces el problema consiste en encontrar un N para el que existan enteros x e y tales que

N = ax + R ₁ y N = by + R ₂ .

Esto es equivalente a

ax−by = c donde c = R ₂ − 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.

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”. ^[1]​

Aryabhata escribió el algoritmo que resuelve la ecuación diofántica lineal en los versos 32-33 de Ganitapada de Aryabhatiya. ^[1]​ 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. ^[1]​
• 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. ^[1]​

Sin pérdida de generalidad, podemos suponer que ⁠${\displaystyle 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 ⁠${\displaystyle \gcd(a,b)}$⁠. Hay dos alternativas: si c no es divisible por ⁠${\displaystyle \gcd(a,b)}$⁠, entonces no hay soluciones enteras para esta ecuación; si sí lo es, habremos obtenido la nueva ecuación ⁠${\displaystyle a'x-b'y=c'}$⁠ cuya solución es también solución de la original ⁠${\displaystyle 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₁ b' + r₁

b' = a₂ r₁+ r₂

r_{1 =} a₃r₂ + r₃'

...

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_mx_m+1 + x_m+2 y entonces y = c' x₁ y x=c' x₂ .

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

   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)

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

   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

El número requerido es 334.

   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 .

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

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.

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.

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², x − y = 4q²

uno obtiene

x = 2(p² + q²), y = 2(p² − q²)

y entonces

xy + 1 = (2p² − 1)² + 4(p² − q⁴).

Para que xy + 1 también sea un cuadrado perfecto debemos tener

p² − q⁴ = 0, that is p² = q⁴.

De esta forma se obtiene la siguiente solución general:

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

El valor q = 2 produce la solución especial x = 40, y = 24.

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

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.

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.

• For a comparison of Indian and Chinese methods for solving linear diophantine equations: A. K. Bag and K. S. Shen (1984). «Kuttaka and Qiuvishu». Indian Journal of History of Science 19 (4): 397-405. Archivado desde el original el 5 de julio de 2015. Consultado el 1 de marzo de 2016. "Kuttaka and Qiuvishu" (PDF). Indian Journal of History of Science. 19 (4): 397–405. Archived from the original (PDF) on 5 July 2015. Retrieved 1 March 2016.
• For a comparison of the complexity of the Aryabhata algorithm with the complexities of Euclidean algorithm, Chinese remainder theorem and Garner's algorithm: T. R. N. Rao and Chung-Huang Yang (2006). «Aryabhata Remainder Theorem: Relevance to Public Key Crypto-systems». Circuits, System, Signals Processing 25 (1): 1-15. Consultado el 1 de marzo de 2016. "Aryabhata Remainder Theorem: Relevance to Public Key Crypto-systems" (PDF). Circuits, System, Signals Processing. 25 (1): 1–15. Retrieved 1 March 2016.
• For a popular readable account of the Kuttaka: Amartya Kumar Dutta (October 2002). «Mathematics in Ancient India 2. Diophantine Equations: The Kuttaka». Resonance 7 (10): 6-22. Consultado el 1 de marzo de 2016. "Mathematics in Ancient India 2. Diophantine Equations: The Kuttaka" (PDF). Resonance. 7 (10): 6–22. Retrieved 1 March 2016.Uso incorrecto de la plantilla enlace roto (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
• For an application of Kuttaka in computing full moon days: Robert Cooke. «Euclid's Algorithm». Archivado desde el original el 15 de junio de 2016. Consultado el 1 de marzo de 2016. "Euclid's Algorithm" (PDF). Archived from the original (PDF) on 15 June 2016. Retrieved 1 March 2016.
• For a discussion of the computational aspects of Aryabhata algorithm: Subhash Kak (1986). «Computational Aspects of Aryabhata Algorithm». Indian Journal of History of Science 21 (1): 62-71. Consultado el 1 de marzo de 2016. "Computational Aspects of Aryabhata Algorithm" (PDF). Indian Journal of History of Science. 21 (1): 62–71. Retrieved 1 March 2016.
• For the interpretation of Aryabhata's original formulation of algorithm: Bibhutibhusan Datta (1932). «Elder Aryabhata's Rule for the Solution of Indeterminate Equations of the First Degree». Bulletin of Calcutta Mathematical Society 24 (1): 19-36. "Elder Aryabhata's Rule for the Solution of Indeterminate Equations of the First Degree". Bulletin of Calcutta Mathematical Society. 24 (1): 19–36.
• For a detailed exposition of the Kuttaka algorithm as given by Sankaranarayana in his commentary on Laghubhaskariya: Bhaskaracharya-1 (Translated by K. S. Shukla) (1963). Laghu-Bhskariya. Lucknow University. pp. 103–114. Consultado el 7 de marzo de 2016. Laghu-Bhskariya. Lucknow University. pp. 103–114. Retrieved 7 March 2016.