Kuṭṭaka es un algoritmo para encontrar soluciones enteras de ecuaciones diofánticas lineales . Una ecuación Diophantine lineal es una ecuación de la forma ax + por = c donde x y y son cantidades desconocidas y un , b , y c son conocidos cantidades con valores enteros. El algoritmo fue inventado originalmente por el astrónomo-matemático indio Āryabhaṭa (476–550 d.C.) y se describe muy brevemente en su Āryabhaṭīya.. Āryabhaṭa no le dio al algoritmo el nombre de Kuṭṭaka , y su descripción del método fue en su mayoría oscura e incomprensible. Fue Bhāskara I (c. 600 - c. 680) quien dio una descripción detallada del algoritmo con varios ejemplos de astronomía en su Āryabhatiyabhāṣya , quien le dio al algoritmo el nombre de Kuṭṭaka . En sánscrito , la palabra Kuṭṭaka significa pulverización (reducción a polvo) e indica la naturaleza del algoritmo. En esencia, el algoritmo es un proceso en el que los coeficientes de una ecuación diofántica lineal dada se dividen en números más pequeños para obtener una ecuación diofántica lineal con coeficientes más pequeños. En general, es fácil encontrar soluciones enteras de ecuaciones diofánticas lineales con coeficientes pequeños. De una solución a la ecuación reducida, se puede determinar una solución a la ecuación original. Muchos matemáticos indios posteriores a Aryabhaṭa han discutido el método Kuṭṭaka con variaciones y refinamientos. Se consideró que el método Kuṭṭaka era tan importante que toda la materia de álgebra solía llamarse Kuṭṭaka-ganita o simplemente Kuṭṭaka . A veces, el tema de la resolución de ecuaciones diofánticas lineales también se llama Kuṭṭaka .
En la literatura, hay varios otros nombres para el algoritmo de Kuṭṭaka como Kuṭṭa , Kuṭṭakāra y Kuṭṭikāra . También hay un tratado dedicado exclusivamente a la discusión de Kuṭṭaka. Estos tratados especializados son muy raros en la literatura matemática de la antigua India. [1] El tratado escrito en sánscrito se titula Kuṭṭākāra Śirōmaṇi y está escrito por un Devaraja. [2]
El algoritmo de Kuṭṭaka tiene mucha similitud y puede considerarse como un precursor del algoritmo euclidiano extendido de hoy en día . Este último algoritmo es un procedimiento para encontrar los números enteros x e y satisface la condición ax + por = gcd ( a , b ). [3]
Formulación del problema de Aryabhaṭa
El problema que supuestamente puede resolverse mediante el método Kuṭṭaka no fue formulado por Aryabhaṭa como un problema de resolución de la ecuación diofántica lineal. Aryabhaṭa consideró los siguientes problemas, todos los cuales son equivalentes al problema de resolver la ecuación diofántica lineal:
- Encuentre un número entero que cuando se divide por dos números enteros dados deja dos residuos dados . Este problema puede formularse de dos formas distintas:
- Deje que el número entero que se encuentra para ser N , los divisores ser un y b , y los restos sean R 1 y R 2 . Entonces el problema es encontrar N tal que
- N ≡ R 1 (mod a ) y N ≡ R 2 (mod b ).
- Dejar que el número entero que se encuentra para ser N , los divisores ser un y b , y los restos sean R 1 y R 2 , el problema es encontrar N tal que no son números enteros x e y tales que
- N = ax + R 1 y N = por + R 2 .
- Esto es equivalente a
- ax - por = c donde c = R 2 - R 1 .
- Encuentre un número entero tal que su producto con un número entero dado que sea aumentado o disminuido por otro entero dado y luego dividido por un tercer número entero no deje resto . Dejar que el número entero a ser determinado sea x y los tres números enteros sea una , b y c , el problema es encontrar x tal que ( ax ± b ) / c es un número entero y . Esto es equivalente a encontrar números enteros x e y tales que
- ( ax ± b ) / c = y .
- Esto, a su vez, es equivalente al problema de 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 una solución si y sólo si mcd ( a , b ) es un divisor de c ". Así que la primera etapa en la pulverización proceso es para cancelar el gcd factor común ( un , b ) a partir de un , b y c , y obtener una ecuación con coeficientes más pequeños en los que los coeficientes de x y y son relativamente primos .
Por ejemplo, Bhāskara I observa: "El dividendo y el divisor se convertirán en primos entre sí, al ser divididos por el residuo de su división mutua. El funcionamiento del pulverizador debe considerarse en relación con ellos". [1]
El algoritmo de Aryabhata
Aryabhata dio el algoritmo para resolver la ecuación diofántica lineal en los versículos 32-33 de Ganitapada de Aryabhatiya. [1] Tomando también en consideración la explicación de Bhāskara I de estos versículos, Bibhutibbhushan Datta ha dado la siguiente traducción de estos versículos:
- "Divida el divisor correspondiente al resto mayor por el divisor correspondiente al resto menor. El residuo (y el divisor correspondiente al resto menor) se dividen mutuamente (hasta que el resto se convierta en cero), el último cociente debe multiplicarse por un elemento opcional entero 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) por la diferencia de los residuos (coloque los otros cocientes de la división mutua sucesivamente uno debajo del otro en una columna; debajo de ellos el resultado que se acaba de obtener y debajo el entero opcional.) Cualquier número debajo (es decir, el penúltimo) se multiplica por el que está justo encima y se suma por el que está justo debajo. Divida el último número ( obtenido al hacerlo repetidamente) por el divisor correspondiente al resto menor; luego multiplique el residuo por el divisor correspondiente al resto mayor y sume el resto mayor (el resultado será l sea) el número correspondiente a los dos divisores ".
Algunos comentarios están en orden.
- El algoritmo produce el número entero positivo más pequeño que da restos especificados cuando se divide por números dados.
- La validez del algoritmo se puede establecer traduciendo el proceso a notaciones matemáticas modernas. [1]
- Los matemáticos indios posteriores, incluidos Brahmagupta (628 d.C.), Mahavira (850), Aryabhata II (950), Sripati (1039), Bhāskara II (1150) y Narayana (1350), han desarrollado varias variantes de este algoritmo y también han discutido varios casos especiales. del algoritmo. [1]
Ejemplo
Planteamiento del problema
Considere el siguiente problema:
- "Encuentre un número entero tal que deje un resto de 15 cuando se divide por 29 y un resto de 19 cuando se divide por 45".
Datos
Restos = 15, 19 Mayor resto = 19 Divisor correspondiente al resto mayor = 45 Resto menor = 15 Divisor correspondiente al resto menor = 29 Diferencia de residuos = 19 - 15 = 4
Paso 1: Divisiones mutuas
Dividir 45 entre 29 para obtener el cociente 1 y el resto 16:29) 45 (1 29 ---- Dividir 29 entre 16 para obtener el cociente 1 y el resto 13:16) 29 (1 dieciséis ---- Dividir 16 entre 13 para obtener el cociente 1 y el resto 3:13) 16 (1 13 ---- Dividir 13 entre 3 para obtener el cociente 4 y el resto 1: 3) 13 (4 3 ---- Divida 3 entre 1 para obtener el cociente 3 y el resto 0: 1) 3 (3 1 ---- El proceso de división mutua se detiene aquí. 0
Paso 2: elegir un número entero opcional
Cocientes = 1, 1, 1, 4, 3 Número de cocientes = 4 (un número entero par) (excluyendo el primer cociente) Elija un número entero opcional = 2 (= k) El último cociente = 3 Multiplica el entero opcional por el último cociente = 2 × 3 = 6 Sume 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 primera columna: 1, 1, 4, 3, 2, 4 (contiene 4 cocientes) Calcule los elementos de la segunda columna: 1, 1, 4, 10, 2 (contiene 3 cocientes) Calcule los elementos de la tercera columna: 1, 1, 42, 10 (contiene 2 cocientes) Calcule los elementos de la cuarta columna: 1, 52, 42 (contiene 1 cociente) Calcule los elementos de la quinta 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 los restos
Paso 5: cálculo de la solución
El último número obtenido = 94 El residuo cuando 94 se divide por el divisor correspondiente al resto menor = 7 Multiplica este residuo por el divisor correspondiente al resto mayor = 7 × 45 = 315 Sumar el resto mayor = 315 + 19 = 334
Solución
El número requerido es 334.
Verificación de 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.
Observaciones
El número 334 es el número entero más pequeño que deja los restos 15 y 19 cuando se divide por 29 y 45 respectivamente.
Un ejemplo de Laghubhāskarīya
El siguiente ejemplo tomado de Laghubhāskarīya de Bhāskara I [4] ilustra cómo se utilizó el algoritmo de Kuttaka en los cálculos astronómicos en la India. [5]
Planteamiento del problema
La suma, la diferencia y el producto aumentado por unidad de los residuos de las revoluciones de Saturno y Marte, cada uno es un cuadrado perfecto. Tomando las ecuaciones proporcionadas por lo anterior y aplicando los métodos de tales 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 calcule el ahargana y las revoluciones realizadas por Saturno y Marte en ese tiempo junto con el número de años solares transcurridos.
Alguna información de antecedentes
En la tradición astronómica india, un Yuga es un período que consta de 1.577.917.500 días civiles. Saturno hace 146,564 revoluciones y Marte hace 229,6824 revoluciones en un Yuga. Entonces Saturno produce 146,564 / 1,577,917,500 = 36,641 / 394,479,375 revoluciones en un día. Al decir que el residuo de la revolución de Saturno es x , lo que se quiere decir es que el número fraccionario de revoluciones es x / 394,479,375. De manera similar, Marte produce 229,6824 / 1,577,917,500 = 190,412 / 131,493,125 revoluciones en un día. Al decir que el residuo de la revolución de Marte es y , lo que se quiere decir es que el número fraccionario de revoluciones es y / 131,493,125.
Cálculo de los residuos
Deje x y y denotan los residuos de las revoluciones de Saturno y Marte satisfacer, respectivamente, las condiciones indicadas en el problema. Deben ser tales que cada uno de x + y . x - y y xy + 1 es un cuadrado perfecto.
Configuración
- x + y = 4 p 2 , x - y = 4 q 2
Se obtiene
- x = 2 ( p 2 + q 2 ) , y = 2 ( p 2 - q 2 )
y entonces
- xy + 1 = (2 p 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 , es decir p 2 = q 4 .
Así 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 las 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. Dado que 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 la 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 número 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 yv = 32,202.
Marte
Sea u el valor del ahargana correspondiente al residuo 40 de Marte. Durante u días, Marte habría completado (190,412 / 131,493,125) × u número de revoluciones. Dado que hay un residuo de 40, este número incluiría también el número fraccionario 40 / 131,493,125 de revoluciones. Por lo tanto, durante la 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 número 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 yv = 171.872.
Referencias
- ↑ a b c d e Bibhutibhushan Datta y Avadhesh Narayan Singh (1962). Historia de las matemáticas hindúes Un libro fuente, Parte II . Editorial de Asia. pag. 92.
- ^ Devaraja (1944). Kuttakara Siromani (en sánscrito) . Prensa Anandasrama . Consultado el 7 de marzo de 2016 .
- ^ DE Knuth (1998). El arte de la programación informática Volumen 2 . Pearson Education India , 1998. p. 342. ISBN 9788177583359.
- ^ Bhaskaracharya-1 (Traducido por KS Shukla) (1963). Laghu-Bhskariya . Universidad de Lucknow. pag. 99 . Consultado el 7 de marzo de 2016 .
- ^ Avinash Sathaye. "Un algoritmo de división mejor" (PDF) . Departamento de Matemáticas, Univ. de Kentucky . Consultado el 7 de marzo de 2016 .
Otras lecturas
- Para una comparación de métodos indios y chinos para resolver ecuaciones diofánticas lineales: AK Bag y KS Shen (1984). "Kuttaka y Qiuvishu" (PDF) . Revista India de Historia de la Ciencia . 19 (4): 397–405. Archivado desde el original (PDF) el 5 de julio de 2015 . Consultado el 1 de marzo de 2016 .
- Para una comparación de la complejidad del algoritmo Aryabhata con las complejidades del algoritmo euclidiano, el teorema del resto chino y el algoritmo de Garner: TRN Rao y Chung-Huang Yang (2006). "Teorema del resto de Aryabhata: relevancia para los sistemas de cifrado de clave pública" (PDF) . Circuitos, Sistema, Procesamiento de Señales . 25 (1): 1-15 . Consultado el 1 de marzo de 2016 .
- Para una cuenta legible popular de Kuttaka: Amartya Kumar Dutta (octubre de 2002). "Matemáticas en la India antigua 2. Ecuaciones diofánticas: el Kuttaka" (PDF) . Resonancia . 7 (10): 6-22 . Consultado el 1 de marzo de 2016 .[ enlace muerto permanente ]
- Para una aplicación de Kuttaka en el cálculo de los días de luna llena: Robert Cooke. "Algoritmo de Euclides" (PDF) . Archivado desde el original (PDF) el 15 de junio de 2016 . Consultado el 1 de marzo de 2016 .
- Para una discusión de los aspectos computacionales del algoritmo Aryabhata: Subhash Kak (1986). "Aspectos computacionales del algoritmo Aryabhata" (PDF) . Revista India de Historia de la Ciencia . 21 (1): 62–71 . Consultado el 1 de marzo de 2016 .
- Para la interpretación de la formulación original del algoritmo de Aryabhata: Bibhutibhusan Datta (1932). "Regla del anciano Aryabhata para la solución de ecuaciones indeterminadas de primer grado". Boletín de la Sociedad Matemática de Calcuta . 24 (1): 19–36.
- Para una exposición detallada del algoritmo de Kuttaka como lo da Sankaranarayana en su comentario sobre Laghubhaskariya: Bhaskaracharya-1 (Traducido por KS Shukla) (1963). Laghu-Bhskariya . Universidad de Lucknow. pp. 103 -114 . Consultado el 7 de marzo de 2016 .