Descomposiciones múltiples del tipo x^2+ky^2

Últimamente nos han surgido cuestiones sobre descomposiciones en suma de cuadrados. Recordamos dos:

http://hojaynumeros.blogspot.com.es/2016/09/expresion-cuadratica-x2ky2-n.html
http://hojaynumeros.blogspot.com.es/2017/01/numero-de-descomposiciones-en.html

Siguiendo esta línea, hoy recorreremos aquellos números que se pueden descomponer en una suma del tipo x^2+ky^2, con k>1, x>0, y>0 de varias formas distintas. Expresado así, es un problema bastante general, que se presta a muchos casos y subcasos, por lo que sólo se desarrollarán algunos, con el fin de aprender a tratarlos y sacar alguna posible propiedad.

Hay un hecho que vale para todos ellos, y es que si N admite una descomposición de un tipo dado x^2+ky^2, con k>1, si lo multiplicamos por un cuadrado admitirá el mismo número de descomposiciones al menos, luego muchas soluciones que encontremos engendrarán otras al multiplicarlas por un cuadrado.

Caso k=2

Si deseamos encontrar todas las expresiones de un número de la forma x^2+2y^2, nuestra mejor herramienta es la que hemos presentado hace pocas semanas bajo el nombre de Cartesius, hoja de cálculo especializada en productos cartesianos condicionados. Puedes descargarla en versión para Excel y LibreOffice Calc, así como las instrucciones en la dirección

http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius

En este caso bastará concretar: 2 sumandos, uno de ellos un cuadrado, el otro doble de un cuadrado, y que la suma de ambos sea igual al número propuesto. Por ejemplo, para saber  cuántas descomposiciones de este tipo permite el número 969, daríamos a Cartesius estas instrucciones:

xtotal=2
xt=1..33
x1=suc(n^2)
x2=suc(2*n^2)
suma=969

La primera exige que sean dos sumandos. La segunda fija un rango de búsqueda de 1 al 33, para que no se nos escape ningún cuadrado inferior a 969, y las siguientes determinan un sumando n^2 y otro 2*n^2. Así se recorrerán todas las posibilidades, que resultan ser cuatro. Si copias esas instrucciones en Cartesius (zona de condiciones) y pulsas el botón Iniciar obtendrás estos cuatro sumandos:

Traducidos a nuestra cuestión, equivalen a las igualdades

969=1^2+2*22^2=13^2+2*20^2=29^2+2*8^2=31^2+2*2^2

No seguiremos por ahí. Nos interesa buscar números con este tipo de propiedad, y podemos dejar Cartesius solo para comprobar. Nos pasamos al VisualBasic de las hojas de cálculo.

Es fácil diseñar una función que recorra todas las posibilidades de suma del tipo x^2+ky^2 para un número dado. El que tenga forma de función nos permite construir tablas para distintos valores, cosa imposible con Cartesius. Proponemos esta:

Public Function numsumacuad(n, k)  ‘Tiene dos parámetros, el número n y k
Dim x, p

p = 0 ‘Iniciamos el contador a cero
For x = 1 To Sqr(n - k) ‘Al estar x elevada al cuadrado, será inferior a una raíz cuadrada
If escuad((n - x ^ 2) / k) Then p = p + 1 ‘Si la diferencia dividida entre k es cuadrado, vale
Next x
numsumacuad = p ‘Contamos las veces
End Function

Esta función no se puede aplicar a 1, pero ya sabemos que no es suma de cuadrados no nulos.

Así podemos formar tablas como esta:

Vemos que entre 20 y 30 solo tienen solución 22, 24 y 27, y esta, doble. Todos los números que admiten al menos una de estas descomposiciones, se podrán representar como suma de tres cuadrados simétricos. Es sólo una curiosidad, pero atractiva. Así, 24=2^2+4^2+2^2

Este número de soluciones, asignando un 0 al 1, está publicada en http://oeis.org/A216278

Destacamos en negrita el intervalo entre 20 y 30.
0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 2, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 2…

Con la función numsumacuad podemos seleccionar aquellos números que admiten dos representaciones (al menos) distintas del tipo x^2+2y^2. Los primeros son estos:

27, 33, 51, 54, 57, 66, 81, 99, 102, 108, 114, 123, 129, 132, 153, 162, 171, 177, 187, 198, 201, 204, 209, 216, 219, 228, 243, 246, 249, 258, 264, 267, 291, 297, 306, 321, 323, 324, 339, 342, 354, 363, 369, 374, 387, 393, 396, 402, 408, 411, 417, 418, 432, 438, 451, 456, 459, 473, 486, 489, 492, 498,…

Todos los números de la sucesión son compuestos, pues Fermat, Euler y Gauss demostraron que los números primos sólo podían descomponerse como x^2+2y^2 de forma única, y no todos, porque deberían ser congruentes con 1 o 3 respecto al módulo 8.

En esta tabla figuran los primeros números primos que se pueden descomponer de la forma dada, y vemos que sus restos son 1 o 3 módulo 8. Un buen ejercicio es adivinar la descomposición en cuadrados mentalmente: 73=1^2+2*6^2, 89=9^2+2*2^2,…

En este tipo de búsquedas siempre recomendamos el lenguaje PARI como complemento o ampliación. En esta cuestión el código adecuado sería, por ejemplo:

for(n=3,500,p=0;for(x=1,sqrtint(n-2),if(issquare((n - x ^ 2) / 2),p+=1));if(p>1,print1(n,", ")))

Si cambiamos la condición p>1 por p==2 obtendremos los números que admiten exactamente dos descomposiciones del tipo que estamos estudiando:

27, 33, 51, 54, 57, 66, 81, 102, 108, 114, 123, 129, 132, 162, 177, 187, 201, 204, 209, 216, 219, 228, 246, 249, 258, 264, 267, 291, 321, 323, 324, 339, 354, 374, 393, 402, 408, 411, 417, 418, 432, 438, 451, 456, 473, 489, 492, 498,…

Vemos que faltan algunos, como el 99, que admiten más de una descomposición.
En todos estos números se dará la siguiente igualdad

N= a²+2b²=c²+2d²  que equivale a (a+c)(a-c)=2(d+b)(d-b)

De esa identidad se deduce que a y c han de tener la misma paridad, para que coincida con el múltiplo de 2 del segundo miembro, pero entonces (a+c)(a-c) será múltiplo de 4, lo que obliga a que también d y b tengan la misma paridad.

Lo puedes comprobar con los ejemplos.

Algunos de estos elementos son cuadrados

81, 324, 729, 1089, 1296, 2025, 2601, 2916, 3249, 3969, 4356, 5184, 6561, 8100, 9801,…

En ellos se cumple que n²=x²+2y², o bien (n²-x²)/2=y², es decir, que (n+x)(n-x)/2=y^2. Podemos interpretar que estos números generan triángulos de catetos enteros cuya área coincide con la de un cuadrado. Por ejemplo, tomamos 1089=33^2. Según nuestra hoja Cartesius admite cuatro descomposiciones del tipo deseado:

Si tomo la segunda, tendré: n=33, x=17, y=20, y se cumple 33²=17²+2*20², y aplicando los cálculos anteriores, se puede formar el triángulo de lados (33+17, 33-17), es decir 50 y 16, con área 50*16/2=400=20², que efectivamente, es un cuadrado.

Con el primero: (33+11,33-11) se convierte en los lados 44 y 22 de área 44*22/2=484=22^2.

Tipo x^2+3y^2

Este caso ofrece menor interés. Estos son los primeros números que admiten más de una descomposición de ese tipo:

Con más de un caso de sumas de cuadrados

28, 52, 76, 84, 91, 112, 124, 133, 148, 156, 172, 196, 208, 217, 228, 244, 247, 252, 259, 268, 273, 292, 301, 304, 316, 336, 343, 364, 372, 388, 399, 403, 412, 427, 436, 444, 448, 468, 469, …

Los puedes generar con este código PARI o con Cartesius o nuestra función en Visual Basic para Excel.

for(n=4,1000,p=0;for(x=1,sqrtint(n-3),if(issquare((n - x ^ 2) / 3),p+=1));if(p>1,write1("final.txt",n,", ")))

Por ejemplo, 469 se descompone como

469=13^2+3*10^2=19^2+3*6^2

Podemos seguir con otros números de casos. Por ejemplo, con tres o más descomposiciones están:

28, 52, 76, 84, 112, 124, 148, 156, 172, 196, 208, 228, 244, 252, 268, 292, 304, 316, 336, 364, 372, 388, 412, 436, 444, 448, 468, 496,…

Vemos que falta el 469, pero no el 468, que admite tres descomposiciones:
468=6²+3*12²=15²+3*9²=21²+3*3²

Puedes intentar descubrir casos llamativos. Un ejemplo: 2548 es el primero con nueve descomposiciones distintas. Insertamos el desarrollo con Cartesius. Las columnas X4 y X5 son los valores de x e y respectivamente:

Tipo x^2+4y^2

Su interés radica en que produce sumas simétricas de cinco cuadrados. No lo estudiaremos. Tan sólo un ejemplo:

464=10^2+10^2+8^2+10^2+10^2


Tipo 2x^2+3^y2

También este caso presenta el interés de obtener una suma de cinco cuadrados que sea simétrica y con bases alternantes. También damos un ejemplo:

365 =3^2+13^2+3^2+13^2+3^2

La reiteración mata el interés. Es mejor parar aquí y dejar abiertos otros caminos de investigación.

Expresión cuadrática X^2+kY^2 = N

Hace unos meses publiqué en Twiter, como una curiosidad, esta tabla de desarrollos para el número 4516

No existen muchos números que admitan esas diez expresiones cuadráticas con enteros. En concreto estos son los primeros:

1009, 1129, 1201, 1801, 2521, 2689, 3049, 3361, 3529, 3889, 4036, 4201, 4516, 4561, 4729, 4804, 5209, 5569, 5881, 6841, 7204, 7561, 7681, 8089, 8521, 8689, 8761, 8929, 9081, 9241, 9601, 9769,…

¿Qué hay detrás de esta lista?

Realmente, el problema radica en resolver la ecuación X²+kY²=N, con k>0 buscando soluciones enteras X>1 Y>1, para evitar trivialidades.

Despejando X en X²+kY²=N nos queda

Por tanto, para averiguar si un número se puede desarrollar de esta forma, bastará recorrer los valores de Y entre 1 y la raíz cuadrada de N/k. El valor que dé como resultado un cuadrado en el radicando será válido.

Por ejemplo, hemos afirmado arriba que 4516 se puede desarrollar como X²+9Y², con X>1 e Y>1. Según lo anterior, buscamos la raíz cuadrada de 4516/9, que resulta ser 22 (si tuviera decimales, truncaríamos). Por tanto habrá que ir probando desde Y=1 hasta Y=22 para ver qué valor da un cuadrado perfecto. Si se posee la función ESCUAD (puedes copiarla desde nuestra entrada http://hojaynumeros.blogspot.com.es/2015/02/numeros-especiales-que-son-un-producto.html ) para ver si un número es cuadrado perfecto, lo podemos organizar en una hoja de cálculo.

No hemos encontrado una solución hasta el valor 18, que junto a la raíz cuadrada de 1600 forma la expresión vista en el primer párrafo 40^2+9*18^2=4516

Función esforma(N;k)

Esta búsqueda que hemos efectuado se podría automatizar. Dado un número N y un coeficiente k podemos diseñar una función que devuelva TRUE si es posible la expresión N=X2+KY2 y FALSE en caso contrario. Existe una variante más útil, y es que si la expresión es posible, la devuelva en forma de String, y en caso contrario la frase “NO”.

En el Basic de VBA podría tener este código (añadimos la función ESCUAD por si no la has encontrado)

Public Function escuad(n) As Boolean
If n < 0 Then
escuad = False
Else
If n = Int(Sqr(n)) ^ 2 Then escuad = True Else escuad = False
End If
End Function

Public Function esforma(n, k) As String
Dim a, b, i
Dim es As Boolean
If k <= 0 Then esforma = "NO": Exit Function ‘Para k<=0 no hay solución
a = Int(Sqr(n / k)) ‘Tope de búsqueda
es = False
i = 1
While i <= a And Not es
b = n - k * i * i
If escuad(b) And b > 0 Then es = True: b = Sqr(b) ‘Se encuentra una solución
i = i + 1
Wend
If es Then
esforma = Str$(b) + "^2+" + Str$(k) + "*" + Str$(i - 1) + "^2" ‘Construcción del String
Else
esforma = "NO" ‘No es expresable
End If
End Function

Con esta función podemos construir un esquema para ver si un número admite la expresión N=X²+kY² con un valor de k dado. En esta imagen encontramos el desarrollo de 4516 con coeficiente 5:

Hay que advertir que la función ESFORMA sólo da la primera solución posible, sin descartar que existan otras.

En esta otra imagen se comprueba que el número 1298 no admite la expresión N=X²+7Y²,

Ordenando un poco los cálculos podemos reproducir la imagen con la que comenzamos la entrada (con formato de hoja de cálculo)

En el caso de k=3 nos devuelve una solución distinta, ya que hay más de una, y hemos prolongado la tabla para comprobar que para los valores k=11 y k=13 no existe solución.

Listado de números expresables

Con esta función y un bloque FOR-NEXT podemos encontrar la lista de los primeros números que se pueden expresar como N=X²+kY²  para un valor de k determinado, e incluso con un doble bucle, los que son expresables para varios valores. Así hemos construido la lista de los que son expresables para los valores k=1..10: 1009, 1129, 1201, 1801, 2521, 2689,…

Números que se puedan expresar con los valores de k=1..11 existen muchos menos. Los primeros son: 7561, 10756, 14116, 14281,…

El número 21961 satisface las expresiones para k=1..13 y los números 32356, 35044 y 35281 llegan al valor 14. Llegan hasta el 15 los números 32356, 35044 y 35281. Y así podríamos seguir, con valores cada vez más altos y escasos.

En estos listados están incluidos valores de k que pueden resultar redundantes. Por ejemplo, si un número es expresable como X^2+8Y^2, también lo es como X^2+2(2Y)^2. Así que si comprobamos la expresión X^2+8Y^2 lo estamos haciendo también con X^2+2Y^2. Como los cálculos no eran muy lentos, hemos preferido dejarlos. En otros trabajos similares se suelen estudiar tan solo los valores primos de k.

Aspecto modular

Si nos fijamos en los restos módulo k, es fácil ver que para que N=X²+kY²,  ha de ser N congruente con X²  módulo k, es decir, que N ha de ser un resto cuadrático módulo k. Si se dispone de un listado de esos restos, o un programa que los genere, podemos averiguar para qué polinomios del tipo dado es expresable un número. La hoja que hemos alojado en esta dirección

http://www.hojamat.es/sindecimales/congruencias/herramientas/hoja/congruencias2.xlsm

contiene restos cuadráticos para cada caso

Hemos adaptado provisionalmente esta herramienta para este caso particular. A cada número que probemos le calculamos el resto respecto a k y lo comparamos con la lista de cuadráticos. Esta prueba sólo la efectuaremos para valores de k que sean primos impares. Los demás casos se reducen a este. Vemos unos ejemplos mediante imágenes:

Aquí vemos que el resto 5 no figura en el listado de restos cuadráticos (columna de la izquierda), 1, 4, 6, 9, 10,…módulo 13, por lo que no es expresable para ese coeficiente.

El mismo resultado obtendríamos mediante ESFORMA(4516,13).

Por el contrario, el número 35281 sí es expresable mediante X²+13Y², , ya que su resto respecto al 13 es 12, y ese valor sí figura como resto cuadrático (el último de la primera columna). Lo dejamos aquí por si te apetece profundizar en la teoría de los restos cuadráticos.

La herencia de Euclides (2) La ecuación Ax=B (mod m)

La ecuación AxºB (mod m)

También aquí remitimos a otras páginas para entender las condiciones de esta ecuación. En primer lugar has de conocer la teoría elemental de las congruencias o Aritmética modular. Si no es así, puedes visitar

http://hojamat.es/parra/modular.pdf
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html

Dentro de esta teoría uno de los primeros temas importantes es el de la resolución de la ecuación lineal AxºB (mod m)  y lo traemos aquí por su relación con el algoritmo de Euclides. En efecto, la ecuación dada equivale a exigir que Ax y B se diferencien en un múltiplo de m, es decir, que Ax+Cm=B. Si leíste la entrada anterior, esto te recordará la Identidad de Bezout.

¿Qué sabes de la estructura de anillo? La repasaremos en la siguiente entrada de esta serie. Por ahora sólo tienes que recordar que en el Álgebra Elemental la ecuación Ax=B para números reales se resuelve multiplicando por el inverso de A, si es que lo posee (siendo distinto de cero en este caso), con lo que tendremos A^-1Ax=1x=x=A^-1B, que es una solución para x.

En los anillos en general no todo elemento posee un inverso, es decir, otro elemento que multiplicado por él lo convierta en la unidad (si esa unidad existe – ver http://es.wikipedia.org/wiki/Anillo_unitario).
En el caso de las congruencias, el anillo Z_m de las clases de restos módulo m está formado por las clases  {0,1,2,3,…m-1} a las que llamaremos restos, y en ellos existen algunos  que pueden no tener inverso. Por ejemplo, si m=9 los elementos de Z₉ son los restos {0,1,2,3,…8} y si elegimos el 6, ningún múltiplo de 6 produce un 1 como resto módulo 9. Veamos (haz tú los cálculos mentalmente para practicar):

6*1º6 (mod 9);   6*2º3 (mod 9); 6*3º0 (mod 9); 6*4º6 (mod 9); 6*5º3 (mod 9); 6*6º0 (mod 9); 6*7º6 (mod 9); 6*8º3 (mod 9)

Nunca resulta un producto congruente con 1, luego el 6 carece de inverso.

Si repasas la teoría del anillo Z_m (lo haremos también en la siguiente entrada) descubrirás que los elementos inversibles son los números primos con m. Como estamos hablando del conjunto de restos {0,1,2,3,…m-1}, el número de inversibles coincidirá con la indicatriz de Euler, como también veremos más adelante. Ya ves, todo se relaciona.

En la resolución de A*xºB (mod m) se presentan estos tipos:

1. Si A es primo con m, existe una sola solución x º A^-1*B (mod m), por ser A inversible.

2. Si MCD(A,m)=d, con d mayor que 1, para que exista solución ha de ser B múltiplo de d. En ese caso se simplifican los tres números A, B y m con lo que se pasa al primer caso. Se puede encontrar una primera solución º A^-1*B (mod m) y existirán en total d soluciones, que vienen dadas por la fórmula x_r = x₀+r*m/d (ver las páginas recomendadas)

En la segunda hoja de la herramienta que estamos usando (Euclides.ods o Euclides.xlsx en
http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm) se sigue este procedimiento. Escribimos los tres datos A,B y m. Sin usar macros, la hoja determina si tiene solución o no y si en caso de tenerla es única o múltiple. Si existe, simplifica los datos.

En la imagen se intenta resolver 6Xº4 (mod 10), que tomaremos como ejemplo. La hoja detecta que existen varias soluciones y simplifica 6, 4, 10 a 3, 2 y 5.

El truco está en las celdas I9, I10 y J10. Investiga y aprenderás.

Abajo figura la resolución, que se basa en la rutina Euclides(X,Y) ya explicada en la entrada anterior y en ella se dan estos pasos:

- Se calculan las reducidas y se toma el penúltimo denominador DEN(5)=2, que es un buen candidato a inverso de A (ver la identidad de Bezout en la entrada anterior).

- Se comprueba el último producto cruzado NUM(6)*DEN(5)-DEN(6)*NUM(5)=3*2-1*5=1 y como vale 1, DEN(5)=2 es el inverso por ser 3*2º1 (mod 5. Si el producto cruzado hubiera valido -1 deberíamos haber cambiado de signo.

- Según hemos explicado, la solución será igual a INV(A)*B=2*2=4. En efecto, 6*4º4 (mod 10)

- El MCD(6,4)=2, luego existirán dos soluciones a la ecuación (hablamos en Z₁₀, porque en Z existirían infinitas). Según la teoría, bastará ir sumando el cociente 10/2=5 a las soluciones, lo que nos da (lo ves en la imagen) las soluciones 4 y 9.

Caso homogéneo

Si B es cero, esta ecuación queda como A*x º 0 (mod m) por lo que además de la solución trivial x=0 existirán otras si M.C.D(A,m)>1, y entonces A se confirmará como divisor de cero. Por ejemplo, resuelve con la hoja 6*x º 0 (mod 9) y obtendrás las soluciones 0, 3 y 6, ya que M.C.D(6,9)=3>1. Sin embargo, resuelve 6*x º 0 (mod 7) y sólo obtendrás x=0, ya que en este caso 6 es inversible.

Te proponemos una demostración o comprobación, según te atrevas.

Las diferencias existentes entre las soluciones de la ecuación A*x º B (mod m) son soluciones de la homogénea A*x º 0 (mod m). Inversamente: dada una solución de A*xºB (mod m), si le vamos sumando por separado las soluciones de la homogénea, resulta el conjunto de todas las soluciones de A*x º B (mod m

Nuestro único objetivo ha sido el que veas la relación de la resolución de esta ecuación con el algoritmo de Euclides y que recorras toda la resolución efectuada por la hoja para comprender mejor los detalles de la misma. Cualquier otro aspecto lo podrás ver en las páginas recomendadas, aunque tampoco se puede decir mucho más.

Ecuación de Pell

Se llama ecuación de Pell (por error, porque Pell no la estudió) a la ecuación diofántica cuadrática X² - DY² = 1, con X e Y variables enteras y D número entero positivo no cuadrado perfecto.

Existe una variante con el segundo miembro -1 que se resuelve de forma similar, con algunas restricciones, y también se consideran los casos en los que se trate de cualquier número entero.

En su resolución hay que distinguir dos problemas:

Primera solución

Una primera solución no es difícil de encontrar en general.

(a) Puedes acudir a un simple tanteo entre cuadrados perfectos. Por ejemplo, una solución de X² - 6Y² = 1 es X₀=5 Y₀=2. Con una hoja de cálculo no es tarea muy complicada.

(b) Las fracciones continuas también son útiles en la resolución de esta ecuación. Basta para ello desarrollar la raíz cuadrada de D mediante ellas y, según vimos en una entrada anterior, aprovechar la periodicidad del desarrollo. En el caso de la ecuación de Pell basta tomar las reducidas anteriores a la finalización del primer periodo.

En la imagen observarás que la solución X₀=5,Y₀=2 aparece antes del final del primer periodo [2,4] en el desarrollo por fracciones continuas. Después siguen otras: X=49, Y=20, X=485, Y=198, etc.

En nuestro modelo de hoja de cálculo que recomendamos más abajo basta escribir el valor de D y el segundo miembro +1 ó -1 y la hoja se encarga de desarrollar la raíz cuadrada de D mediante fracciones continuas:

(c) En el documento recomendado al final de esta entrada puedes estudiar estos y otros métodos muy útiles.

Siguientes soluciones

Según la teoría del anillo  Q(R), siendo R la raíz cuadrada de D (no lo desarrollaremos aquí), las primeras soluciones, escritas como 

constituyen una unidad del anillo, y también lo serán todas sus potencias, por lo que las siguientes soluciones provendrán de los desarrollos de las expresiones

agrupando después los términos que no contienen el radical como valor de Y y los que sí lo contienen como valor de X. Este método puede ser fatigoso, por lo que es mejor ir obteniendo las distintas soluciones por recurrencia. En efecto, de la anterior consideración se deduce que

O bien, separando términos:

Estas son las fórmulas que hemos usado en la hoja de cálculo.

Puedes consultar la búsqueda de la primera solución por fracciones continuas y la recurrencia para las siguientes en las hojas de cálculo

http://www.hojamat.es/sindecimales/aritmetica/herramientas/hoja/pell.ods para Calc
http://www.hojamat.es/sindecimales/aritmetica/herramientas/hoja/pell.xls para Excel

Por ejemplo, intenta resolver esta cuestión: ¿Qué cuadrado perfecto de diez cifras, al quitarle una unidad se puede descomponer en cinco cuadrados perfectos idénticos?

Nuestro colaborador Rafael Parra Machío nos ha facilitado un documento muy interesante sobre la ecuación de Pell, en el que podrás consultar otros métodos de resolución, como el que usa aritmética modular, y también algunos detalles históricos y teóricos que no hemos incluido aquí.

Lo puedes descargar desde la dirección http://www.hojamat.es/parra/pell.pdf

Fracciones continuas (3) - Ecuaciones diofánticas

Una aplicación importante de las fracciones continuas y sus reducidas es la de resolver ecuaciones diofánticas lineales del tipo Ax+By=C, en las que C es múltiplo del MCD de A y B (que son las que poseen solución). Quiere esto decir que A,B y C se pueden simplificar hasta conseguir que MCD(A,B)=1. En lo que sigue supondremos que esto se cumple.

Efectivamente, en una entrada anterior se vio que la diferencia entre dos reducidas consecutivas equivalía a una fracción de numerador la unidad y de denominador el producto de sus denominadores. Esta propiedad también se cumple entre la última reducida y la fracción dada.

Vemos cómo se aprovecha esta propiedad para resolver la ecuación.

Sea, por ejemplo, la ecuación 244X+108Y=112.

Simplificamos: 61X+27Y=28, con MCD(61,27)=1

Buscamos las reducidas de la fracción 61/27 y elegimos la última 9/4



Y se cumplirá, según la propiedad citada, que 61*4-27*9=1, luego 4 y -9 serán las soluciones de 61X+27Y=1. Bastará multiplicar por el término independiente 28 para obtener una solución: X=4*28 = 112 e Y=-9*28 = -252

Las demás soluciones se obtienen mediante las paramétricas.

X=112-27t
Y=-252+61t

Si se desean soluciones positivas deberemos ajustar el parámetro t