Métodos para resolver ecuaciones diofánticas de segundo grado

1. Alpertron
2. Teoría de números
3. Métodos para resolver ecuaciones diofánticas de segundo grado

por Dario Alejandro Alpern

El propósito de este artículo es mostrar cómo resolver la ecuación diofántica Ax² + Bxy + Cy² + Dx + Ey + F = 0. El término ecuación diofántica significa que las soluciones (x, y) deben ser números enteros. Por ejemplo, la ecuación 4y² - 20y + 25 = 0 tiene soluciones dadas por la línea horizontal y = 2.5, pero como 2,5 no es un número entero, diremos que la ecuación no tiene soluciones.

Hay algunos casos que dependen de los valores de A, B y C. Los nombres de estos casos se toman de las figuras que la ecuación representa en el plano xy: una línea, una elipse, una parábola o una hipérbola (o dos líneas). Estas figuras son el conjunto de soluciones reales. En nuestra situación, el conjunto de soluciones está representado por puntos aislados en el plano xy.

Contenido

• Caso lineal: A = B = C = 0.
  
  
• Caso hiperbólico simple: A = C = 0; B ≠ 0.
  
  
• Caso elíptico: B² - 4AC < 0.
  
  
• Caso parabólico: B² - 4AC = 0.
  
  
• Caso hiperbólico: B² - 4AC > 0.
  
  
• Programas que usan estos métodos

Caso lineal: A = B = C = 0

• Si D = 0 y E = 0 habrá soluciones sólo si F = 0. En este caso todos los valores de x e y son soluciones.
• Si D = 0 y E ≠ 0 tenemos:
  Ey + F = 0 => y = -F/E, x = cualquier entero.
  Esto significa que habrá soluciones si y sólo si F es múltiplo de E.
• Si D ≠ 0 y E = 0 resulta:
  Dx + F = 0 => x = -F/D, y = cualquier entero.
  Esto significa que habrá soluciones si y sólo si F es múltiplo de D.
• Si D ≠ 0 y E ≠ 0 la situación es un poco más complicada:
  Sea g = mcd(D, E). Como D y E son múltiplos de g, la expresión Dx + Ey también será un múltiplo de g para cualquier valor entero de x e y, por lo que si F no es múltiplo de g, la ecuacion no tiene soluciones.

  Si F es múltiplo de g podemos dividir los tres coeficientes por g obteniendo:
  dx + ey = -f (donde d=D/g, e=E/g y f=F/g). Ahora utilizaremos el algoritmo extendido de Euclides que se utiliza para hallar valores u' y v' enteros tales que uu'+vv' = ±mcd(u, v) (donde el signo depende del signo de d y e y de la implementación del algoritmo).

  Hagamos ahora u = d, v = e. Una vez que se encuentren los valores de u' y v' tales que du'+ev' = ±1 (ya que mcd(d, e)=1) podemos multiplicar la ecuación por -f para obtener:

  du'+ev' = ±1 => d(±fu')+e(±fv') = -f => d(±fu')+det+e(±fv')-det = -f => d(et±fu')+e(-dt±fv') = f

  Así que el conjunto general de soluciones es:

  x = et ± fu'
  y = -dt ± fv'
  t = cualquier entero

mcd(D, E) = mcd(10, 84) = 2. Como el término independiente también es múltiplo de 2, deberemos dividir la ecuación por este mcd.

La ecuación es ahora: 5x + 42y + 8 = 0.

Ahora aplicaremos el algoritmo generalizado de Euclides:

• Paso 1: 1 * 5 + 0 * 42 = 5
• Paso 2: 0 * 5 + 1 * 42 = 42
• Paso 3: 1 * 5 + 0 * 42 = 5
• Paso 4: (-8) * 5 + 1 * 42 = 2
• Paso 5: 17 * 5 + (-2) * 42 = 1

Multiplicando la última ecuación por -F = -8 obtenemos:
(-136) * 5 + 16 * 42 = -8

Sumando y restando de t = 5 * 42 t obtenemos:
(-136 + 42 t) * 5 + (16 - 5 t) * 42 = -8

Así, la solución está dada por el conjunto:

donde t es cualquier número entero.

Caso hiperbólico simple A = C = 0; B ≠ 0

Existen dos casos: DE - BF = 0 (dos líneas paralelas a los ejes x e y respectivamente) y DE - BF ≠ 0 (una hipérbola cuyas asíntotas son paralelas a los ejes x e y).

En el primer caso una condición necesaria para la existencia de soluciones ocurre cuando uno de los paréntesis es igual a cero, es decir, Bx + E = 0 o By + D = 0. Como B ≠ 0, tenemos soluciones para:

En el segundo caso los valores de x e y se pueden hallar a partir de los divisores de DE - BF. Sean d₁, d₂, ..., d_n todos los divisores de DE - BF. Así,

Ejemplo 2: Resolver 2xy + 5x + 56y + 7 = 0.

En este caso los divisores de DE - BF = 5*56 - 2*7 = 266 son: ±1, ±2, ±7, ±14, ±19, ±38, ±133, ±266.

Como (2x + 56) (2y + 5) = 266 obtenemos:

• d₁ = 1: x = (1-56)/2 = -55/2, y = (266/1-5)/2 = 261/2
• d₂ = -1: x = (-1-56)/2 = -57/2, y=[266/(-1)-5]/2 = 271/2
• d₃ = 2: x = (2-56)/2 = -27, y = (266/2-5)/2 = 64
• d₄ = -2: x = (-2-56)/2 = -29, y = [266/(-2)-5]/2 = -69
• d₅ = 7: x = (7-56)/2 = -49/2, y = (266/7-5)/2 = 33/2
• d₆ = -7: x = (-7-56)/2 = -63/2, y = [266/(-7)-5]/2 = -43/2
• d₇ = 14: x = (14-56)/2 = -21, y = (266/14-5)/2 = 7
• d₈ = -14: x = (-14-56)/2 = -35, y = [266/(-14)-5]/2 = -12
• d₉ = 19: x = (19-56)/2 = -37/2, y = (266/19-5)/2 = 9/2
• d₁₀ = -19: x = (-19-56)/2 = -75/2, y = [266/(-19)-5]/2 = -19/2
• d₁₁ = 38: x = (38-56)/2 = -9, y = (266/38-5)/2 = 1
• d₁₂ = -38: x = (-38-56)/2 = -47, y = [266/(-38)-5]/2 = -6
• d₁₃ = 133: x = (133-56)/2 = 77/2, y = (266/133-5)/2 = -3/2
• d₁₄ = -133: x = (-133-56)/2 = -189/2, y = [266/(-133)-5]/2 = -7/2
• d₁₅ = 266: x = (266-56)/2 = 105, y = (266/266-5)/2 = -2
• d₁₆ = -266: x = (-266-56)/2 = -161, y = [266/(-266)-5]/2 = -3

Sólo hay 8 soluciones a la ecuación pedida y son las que están marcadas en rojo.

Caso elíptico B² - 4AC < 0

Como la elipse es una figura cerrada, la cantidad de soluciones será finita.

Operando con la ecuación cuadrática original:

Ax² + Bxy + Cy² + Dx + Ey + F = 0

Cy² + (Bx + E)y + (Ax² + Dx + F) = 0

y = -(Bx + E) ± (Bx + E)2 - 4C(Ax2 + Dx + F) / 2C     (*)

Para cualquier valor de x habrá dos valores de y excepto en los extremos izquierdo y derecho de la elipse. En este caso habrá sólo un valor de y. Para determinar la ubicación de los extremos debemos igualar la raíz cuadrada a cero, así la expresión devolverá sólo un valor de y.

(Bx + E)² - 4C(Ax² + Dx + F) = 0

(B² - 4AC)x² + 2(BE - 2CD)x + (E² - 4CF) = 0

Así que los valores de x deberán estar entre las raíces de esta ecuación. Si las raíces no son reales, no habrá soluciones a la ecuación original, en caso contrario, deberemos reemplazar todos los valores enteros de x en el rango indicado en la ecuación (*) para poder encontrar un valor entero de y.

Ejemplo 3: Resolver 42x² + 8xy + 15y² + 23x + 17y - 4915 = 0.

Como B² - 4AC = 8² - 4*42*15 = -2456 < 0 la ecuación es elíptica.

Los valores de x deberán estar entre las raíces de (B² - 4AC)x² + 2(BE - 2CD)x + (E² - 4CF) = -2456x² - 1108x + 295189 = 0. Las raíces valen -11,19... y 10,74..., así que deberemos verificar los valores de x en el rango de -11 a 10.

El único valor de x que reemplazado en (*) hace que y sea entero ocurre para x = -11, con lo que y = -1, por lo que ésta es la única solución al problema propuesto.

Caso parabólico B² - 4AC = 0

Como b² = 4ac es positivo, podemos elegir g con el mismo signo de A. De esta manera a y c serán positivos (o alguno de los dos cero).

La expresión b² - 4ac = 0 implica que b²/4 = ac. Como mcd(a,c) = 1, tanto a como c son cuadrados perfectos.

Multiplicando la ecuación original por :

g(ax² + bxy + cy²) + Dx + Ey + F = 0

g(x + y)² + Dx + Ey + F = 0

donde el signo de debe ser el mismo que el de B/A.

Sumando y restando Dy:

g(x + y)² + D(x + y) - Dy + Ey + F = 0

Sea u = x + y:    (i)

gu² + Du + (E - D)y + F = 0

(D - E)y = gu² + Du + F (ii)

Existen dos casos: D - E = 0 (dos líneas paralelas) o D - E ≠ 0 (una parábola).

En el primer caso, D - E = 0.

De (ii): gu² + Du + F = 0

Como x e y deben ser números enteros, la ecuación (i) implica que el número u (la raíz de la última ecuación) también debe ser entero. Sean u₁ y u₂ las raíces de la ecuación.

De (i) resulta: x + y - u₁ = 0 y x + y - u₂ = 0 que se pueden resolver con los métodos explicados para la ecuación lineal.

En el segundo caso, gu² + Du + F deberá ser múltiplo de D - E.

Sean u₀, u₁,... los valores de u en el rango 0 ≤ u < |D - E| en los cuales se cumple la condición anterior.

Así u = u_i + (D - E)t, donde t es cualquier número entero.   (iii)

Reemplazando (iii) en (ii):

(D - E)y = g[u_i + (D - E)t]² + D[u_i + (D - E)t] + F

y = g(D - E)t² + (D + 2gu_i)t + gu_i² + Du_i + F / D - E

De (i) y (iii):

u = x + y = u_i + (D - E)t

x = g(E - D)t² + (D - E - 2gu_i - D)t + u_i -   gu_i² + Du_i + F / D - E

x = g(E - D)t² + (- E - 2gu_i)t + u_i(D - E) - gu_i² - Du_i - F / D - E

x = g(E - D)t² + (- E - 2gu_i)t - gu_i² + Eu_i + F / D - E

Ejemplo 4: Hallar las soluciones de 8 x² - 24 xy + 18 y² + 5x + 7y + 16 = 0

Debemos calcular los valores de g, a, c, , , D - E y gu² + Du + F.

g = mcd(8, 18) = 2
a = 8/2 = 4
c = 18/2 = 9
= 2
= -3 (ya que B/A = -24/8 < 0)
D - E = -3 * 5 - 2 * 7 = -29 (segundo caso)
gu² + Du + F = 4u² + 5u + 32

Debemos determinar los valores de u en el rango 0 ≤ u < 29 para los cuales 4u² + 5u + 32 sean múltiplos de 29.

Los valores de u son: u₀ = 2 y u₁ = 4.

Para u₀ = 2:

Para u₀ = 4:

Caso hiperbólico B² - 4AC > 0

Contents

• Hallar soluciones de la ecuación homogénea Ax² + Bxy + Cy² + F = 0
  
  
• Hallar recurrencias entre las soluciones de la ecuación homogénea
  
  
• Hallar soluciones de la ecuación general cuadrática
  
  
• Hallar recurrencias entre las soluciones de la ecuación general cuadrática

Hallar soluciones de la ecuación homogénea Ax² + Bxy + Cy² + F = 0

Ax² + Bxy + Cy² = -F

Multiplicando por 4A:
4A²x² + 4ABxy + 4ACy² = -4AF
4A²x² + 4ABxy + B²y² - B²y² + 4ACy² = -4AF
(2Ax + By)² - (B² - 4AC)y² = -4AF

Esto se puede interpretar como una diferencia de cuadrados:

(2Ax + By + B2 - 4AC y) (2Ax + By - B2 - 4AC y) = -4AF
(2Ax + (B +  B2 - 4AC )y) (2Ax + (B - B2 - 4AC )y) = -4AF

Como -4AF = 0, la condición para tener más soluciones es que B² - 4AC sea un cuadrado perfecto.

Para hallar las soluciones en este caso se puede utilizar el método para las ecuaciones lineales (porque la ecuación se puede representar en el plano xy mediante dos líneas rectas que se intersectan en el punto (0, 0)).

Si F ≠ 0 y B² - 4AC = k² para algún entero k, los paréntesis en la ecuación anterior deben ser factores de -4AF.

Sean u₁, u₂,... los divisores positivos y negativos de -4AF.

Entonces tenemos el siguiente conjunto de dos ecuaciones lineales en dos incógnitas:

2Ax + (B+k)y = u_i
2Ax + (B-k)y = -4AF/u_i

Por lo tanto:

y = u_i + 4AF/u_i / 2k

x = u_i - (B+k)y / 2A

Debemos descartar los valores de u_i que hagan x o y no enteros.

Consideraremos ahora el caso F ≠ 0 y B² - 4AC no un cuadrado perfecto.

Si F no es múltiplo de mcd(A, B, C), la ecuación no tiene soluciones, de otra manera podemos dividir todos los coeficientes de la ecuación por este mcd.

Si 4 F² < B² - 4AC, la solución de la ecuación estará entre los convergentes de la fracción continua de las raíces de la ecuación At² + Bt + C = 0.

Como el desarrollo en fracción continua de una irracionalidad cuadrática es periódica, si B² - 4AC no es un cuadrado perfecto la cantidad de soluciones será infinita o ninguna.

Por otra parte, si 4 F² ≥ B² - 4AC las soluciones se pueden obtener como sigue:

Sean G = mcd(x,y), x = Gu e y = Gv.

La ecuación original se convierte en: AG²u² + BG²uv + CG²v² + F = 0, así que F será múltiplo de G².

Dividiendo la ecuación por G²:

Au² + Buv + Cv² + F/G² = 0    (1).

Una vez hallados los valores de u y v, podemos determinar fácilmente x = Gu e y = Gv.

Así que podemos asumir que mcd(x,y) = 1.

Sea x = sy - Fz    (2).

Reemplazando en la ecuación original:

A(sy - Fz)² + B(sy - Fz)y + Cy² + F = 0

As²y² - 2AFsyz + AF²z² + Bsy² - BFyz + Cy² = -F

(As² + Bs + C) y² + (-2As - B)Fyz + AF²z² = - F

Dividiendo por -F:

-(As² + Bs + C) y² / F + (2As + B)yz - AFz² = 1    (3)

Ahora debemos determinar los valores de s entre 0 y F - 1 tales que As² + Bs + C ≡ 0 (mod F). Una vez que los valores de y y z se determinan usando el desarrollo en fracción continua de las raíces de -(As² + Bs + C) t² / F + (2As + B)t - AF = 0, el valor de x se determina mediante (2). Si no se encuentran soluciones entre los convergentes, no habrá soluciones a (1).

Si la ecuación original tiene soluciones, entonces debe haber una solución a la congruencia anterior, excepto cuando mcd(A,B,F) > 1. En este caso, si mcd(B,C,F) = 1 debemos hacer la sustitución y = sx - Fz    (4). Reemplazando en la ecuación original:

Ax² + Bx(sx - Fz) + C(sx - Fz)² + F = 0

Ax² + Bsx² - BFxz + Cs²x² - 2CFsxz + CF²z² = -F

(Cs² + Bs + A) x² + (-2Cs - B)Fxz + CF²z² = - F

Dividiendo por -F:

-(Cs² + Bs + A) x² / F + (2Cs + B)xz - CFz² = 1    (5).

Ahora debemos determinar los valores de s entre 0 y F - 1 tales que Cs² + Bs + A ≡ 0 (mod F). Una vez determinados los valores de x y z usando el desarrollo en fracción continua de las raíces de -(Cs² + Bs + A) t² / F + (2Cs + B)t - CF = 0, el valor de y se determina mediante (4). Si no se encuentran soluciones entre los convergentes, no habrá soluciones a (1).

Las ecuaciones (4) y (5) no tienen soluciones cuando mcd(A,B,F) y mcd(B,C,F) son ambos mayores que 1. En este caso usaremos el siguiente método:

Sean i, j, m y n cuatro números enteros tales que in - jm = 1    (6).

Si x = iX + jY e y = mX + nY    (7) obtenemos X = nx - jy e Y = -mx + iy    (8).

Como esta transformación es reversible, podemos convertir cualquier (x,y) en (X,Y) y viceversa. Así que trabajaremos con (X,Y) y con estas soluciones calcularemos los valores de (x,y) que satisfagan la ecuación original.

Ax² + Bxy + Cy² =
= A(iX+jY)² + B(iX+jY)(mX+nY) + C(mX+nY)² =
= aX² + bXY + cY²

donde:

a = Ai² + Bim + Cm²    (9)
b = 2Aij + Bin + Bjm + 2Cmn    (10)
c = Aj² + Bjn + Cn²    (11)

Debemos hallar los valores de i y m tales que a = Ai² + Bim + Cm² sea relativamente primo a F.

Como mcd(C, F) > 1 resulta mcd(Ai² + Bim + Cm², C) = 1, así mcd(i, C) = 1 y mcd(Ai+Bm, C) = 1.

Como mcd(A, F) > 1 resulta mcd(Ai² + Bim + Cm², A) = 1, así mcd(m, A) = 1 y mcd(Bi+Cm, A) = 1.

De (6), mcd(i, m) = 1.

Si F ≡ 0 (mod p) (p primo):

i y m según a, b y c

A	B	C	i, m	Ejemplos
A ≡ 0	B ≡ 0	C ≡ 0	No se aplica (mcd(A, B, C) = 1)
A ≡ 0	B ≡ 0	C 0	m 0	i ≡ 0, m ≡ 1
A ≡ 0	B 0	C ≡ 0	i 0, m 0	i ≡ 1, m ≡ 1
A ≡ 0	B 0	C 0	m 0, i -Cm/B	i ≡ 1-C, m ≡ B
A 0	B ≡ 0	C ≡ 0	i 0	i ≡ 1, m ≡ 0
A 0	B ≡ 0	C 0	i 0 o m 0	i ≡ 1, m ≡ 1
A 0	B 0	C ≡ 0	i 0, m -Ai/B	i ≡ B, m ≡ 1-A
A 0	B 0	C 0	i 0 o m 0	i ≡ 1, m ≡ 1

Aunque se pueden generar los valores de i y m a partir de sus valores modulo primos diferentes, es muy tedioso y no es necesario, porque de la tabla que se acaba de mostrar, se pueden utilizar casi todos los valores de i y m, por lo que es mejor utilizar el siguiente pseudocódigo para poder hallar ambos valores:

  for i=0 to |F|-1
    for m=0 to i+1
      if gcd(i, m) = 1
        k = Ai2 + Bim + Cm2
        if gcd(k, F) = 1, end.
      end if
    next m
  next i


Con los valores de i y m que se acaban de hallar, podemos calcular los valores de j y n mediante (6) usando los métodos para la ecuación lineal. Luego debemos calcular a, b y c usando (9), (10) y (11), para poder hallar el conjunto de soluciones (X,Y). Con la fórmula (7) podemos hallar el conjunto de soluciones (x,y).

Créditos:

Este método me lo envió Iain Davidson por correo electrónico. Yo introduje algunos cambios.

Ejemplo 5: Encontrar algunas soluciones de 18 x² + 41 xy + 19 y² - 24 = 0

Lo primero que se debe hacer es determinar el mcd de todos los coeficientes excepto el independiente, esto es: mcd(18, 41, 19) = 1.

Dividiendo la ecuación por el máximo común divisor obtenemos:
18 x² + 41 xy + 19 y² - 24 = 0

Nos encontramos en el caso 4f² ≥ b² - 4ac.

Sea x = sy - fz, luego [-(as² + bs + c)/f]y² + (2sa + b)yz - afz² = 1.

Así 18 s² + 41 s + 19 debe ser múltiplo de 24.

Esto se cumple para s = 19.

• Sea s = 19. Reemplazando en la ecuación indicada arriba:
  304 y² + 725 yz + 432 z² = 1

  Debemos hallar el desarrollo en fracción continua de las raíces de 304 t² + 725 t + 432 = 0, esto es, t = √313 - 725 / 608

  El desarrollo en fracciones continuas es:
  -2 + //1, 5, 8, 5, 1, 3, 1, 1, 2, 2, 1, 1, 3, 1, 5, 8, 1, 2, 17, 2, 1//

  donde la parte periódica está marcada en negrita (el período tiene 19 coeficientes).

  La siguiente tabla muestra como se hallan los valores de Y₀ y Z₀ (en la tercera columna se encuentran los valores de P(y, z) = 304 y² + 725 yz + 432 z²):

  Términos de la fracción continua y convergentes

  cn	yn	zn	P(yn, zn)
  	1	0
  -2	-2	1	198
  1	-1	1	11
  5	-7	6	-2
  8	-57	49	3
  5	-292	251	-12
  1	-349	300	4
  3	-1339	1151	-9
  1	-1688	1451	8
  1	-3027	2602	-6
  2	-7742	6655	6
  2	-18511	15912	-8
  1	-26253	22567	9
  1	-44764	38479	-4
  3	-160545	138004	12
  1	-205309	176483	-3
  5	-1 187090	1 020419	2
  8	-9 702029	8 339835	-11
  1	-10 889119	9 360254	6
  2	-31 480267	27 060343	-1
  17	-546 053658	469 386085	6
  2	-1123 587583	965 832513	-11
  1	-1669 641241	1435 218598	2
  8	-14480 717511	12447 581297	-3
  5	-74073 228796	63673 125083	12
  1	-88553 946307	76120 706380	-4
  3	-339735 067717	292035 244223	9
  1	-428289 014024	368155 950603	-8
  1	-768024 081741	660191 194826	6
  2	-1 964337 177506	1 688538 340255	-6
  2	-4 696698 436753	4 037267 875336	8
  1	-6 661035 614259	5 725806 215591	-9
  1	-11 357734 051012	9 763074 090927	4
  3	-40 734237 767295	35 015028 488372	-12
  1	-52 091971 818307	44 778102 579299	3
  5	-301 194096 858830	258 905541 384867	-2
  8	-2461 644746 688947	2116 022433 658235	11
  1	-2762 838843 547777	2374 927975 043102	-6
  2	-7987 322433 784501	6865 878383 744439	1
  17	-138547 320217 884294	119094 860498 698565	-6
  2	-285081 962869 553089	245055 599381 141569	11
  1	-423629 283087 437383	364150 459879 840134	-2

  Nótese que y_n = c_n y_n-1 + y_n-2 y z_n = c_n z_n-1 + z_n-2.

  Los signos en la tercera columna son alternados, así que los números se repetirán después de una cantidad par de convergentes. Por lo tanto deberemos considerar dos períodos si la longitud del período es impar. Si es par, sólo debemos considerar un período. Con estas soluciones y la recurrencia que será desarrollada en la próxima sección, obtendremos todas las soluciones de la ecuación homogénea.

  Y₀ = -7987 322433 784501 16
  Z₀ = 6865 878383 744439 16
  Como X₀ = 19 Y₀ + 24 Z₀:
  

  X₀ = 13021 954967 961017 17
  Y₀ = -7987 322433 784501 16

  Como la ecuación Ax² + Bxy + Cy² + F = 0 no cambia cuando x se reemplaza por -x e y se reemplaza por -y simultáneamente, tenemos otra solución:

  X₀ = -13021 954967 961017 17
  Y₀ = 7987 322433 784501 16

  Ahora debemos considerar el desarrollo en fracción continua de la otra raíz: t = - √313 + 725 / 608

  Esto es -2 + //1, 3, 1, 1, 17, 2, 1, 8, 5, 1, 3, 1, 1, 2, 2, 1, 1, 3, 1, 5, 8, 1, 2// (el período tiene 19 coeficientes).

  La siguiente tabla muestra cómo se hallan los valores de Y₀ y Z₀ (en la tercera columna se encuentran los valores de P(y, z) = 304 y² + 725 yz + 432 z²):

  Términos de la fracción continua y convergentes

  cn	yn	zn	P(yn, zn)
  	1	0
  -2	-2	1	198
  1	-1	1	11
  3	-5	4	12
  1	-6	5	-6
  1	-11	9	1
  17	-193	158	-6
  2	-397	325	11
  1	-590	483	-2
  8	-5117	4189	3
  5	-26175	21428	-12

  Esta tabla no es completa, pero no hay soluciones en la sección no mostrada.

  Y₀ = 11
  Z₀ = -9
  Como X₀ = 19 Y₀ + 24 Z₀:

  X₀ = -7
  Y₀ = 11
  
  
  X₀ = 7
  Y₀ = -11

Debemos hallar el desarrollo en fracción continua de las raíces de 18 t² + 41 t + 19 = 0, esto es, t = √313 - 41 / 38

El desarrollo es:
-1 + //2, 1, 5, 8, 1, 2, 17, 2, 1, 8, 5, 1, 3, 1, 1, 2, 2, 1, 1, 3//

donde la parte periódica está marcada en negrita (el período tiene 19 coeficientes).

La siguiente tabla muestra cómo se hallan los valores de U₀ y V₀ (en la tercera columna se encuentran los valores de P(u, v) = 18 u² + 41 uv + 19 v²):

Como se explicó arriba, x = 2u e y = 2v, así que:

La otra raíz de la ecuación 18 t² + 41 t + 19 = 0 es t = - √313 + 41 / 38

Su desarrollo en fracción continua es:
-2 + //2, 1, 2, 2, 1, 1, 3, 1, 5, 8, 1, 2, 17, 2, 1, 8, 5, 1, 3, 1//

donde la parte periódica está marcada en negrita (el período tiene 19 coeficientes).

La siguiente table muestra cómo se hallan los valores de U₀ y V₀ (en la tercera columna se encuentran los valores de P(u, v) = 18 u² + 41 uv + 19 v²):

Como se explicó arriba, x = 2u e y = 2v, así que:

Hallar recurrencias entre las soluciones de la ecuación homogénea

X_n+1 = P X_n + Q Y_n
Y_n+1 = R X_n + S Y_n

donde se deben determinar P, Q, R y S.

Sea M(x, y) = Ax² + Bxy + Cy² = M y N(u, v) = u² + Buv + ACv² = N.

M(p, q) = Ap² + Bpq + Cq²

M(p, q)/A = p² + (B/A)pq + (C/A)q²

M(p, q)/A = p² + Dpq + Eq²

M(p/q, 1)/A = (p/q)² + D(p/q) + E    (12)

Las raíces de M(p/q, 1)/A = (p/q - J) (p/q - J') = 0  (13) son:

J = -B + B2 - 4AC / 2A y J' = -B - B2 - 4AC / 2A

Se puede mostrar fácilmente igualando (12) y (13) que:

J² = -DJ - E    (14)
J'² = -DJ' - E    (15)
J + J' = -D    (16)
JJ' = E    (17)

Las raíces de N(p/q, 1) = (p/q - K) (p/q - K') = 0 son:

K = -B + B2 - 4AC / 2A y K' = -B - B2 - 4AC / 2A

así que K = AJ, K' = AJ'    (18)

M(p, q)/A = (p - Jq)(p - J'q) = M    (19)

N(r, s) = (r - Ks)(r - K's) = N    (20)

De (18) obtenemos:

(p - Jq)(r - Ks) = (p - Jq)(r - AJs) = (pr - AJps - Jqr + AJ²qs)

De (14) resulta:

[pr - AJps - Jqr + A(-DJ - E)qs] = (pr - AEqs) - (Aps + qr + AEqs)J = (pr - Cqs) - (Aps + qr + Bqs)J    (21)

De (18) obtenemos:

(p - J'q)(r - K's) = (p - J'q)(r - AJ's) = (pr - AJ'ps - J'qr + AJ'²qs)

De (15) resulta:

[pr - AJ'ps - J'qr + A(-DJ' - E)qs] = (pr - AEqs) - (Aps + qr + AEqs)J' = (pr - Cqs) - (Aps + qr + Bqs)J'    (22)

Sean X = pr - Cqs e Y = Aps + qr + Bqs    (23).

Multiplicando (21) por (22) obtenemos:

(M(p, q)/A) N(r, s) = (X - YJ) (X - YJ') = X² - (J + J')XY + JJ'Y²

Multiplicando las ecuaciones (16) y (17) obtenemos: (M(p, q)/A) N(r, s) = X² + DY + EY²

Multiplicando por A obtenemos (de (19) y (20)):

AX² + BXY + CY² = MN

Haciendo M = -F y N = 1 podemos observar que X e Y también son soluciones de la ecuación original.

Sea r y s una solución a N(r, s) = r² + Brs + ACs² = 1,
X_n = p, Y_n = q, X_n+1 = X e Y_n+1 = Y (ya que los dos últimos pares de números son soluciones de la ecuación original).

De (23) obtenemos:

X_n+1 = rX_n - CsY_n+1
Y_n+1 = AsX_n + rY_n+1 + BsY_n+1

Esto significa que:

Créditos: Este método me lo envió Iain Davidson. Yo hice algunas modificaciones.

Hallar soluciones de la ecuación cuadrática general

Multiplicando la ecuación por 4A:

4A²x² + 4ABxy + 4ACy² + 4ADx + 4AEy + 4AF = 0
(2Ax + By + D)² - (By + D)² + 4ACy² + 4AEy + 4AF = 0
(2Ax + By + D)² + (4AC - B²)y² + (4AE - 2BD)y + (4AF - D²) = 0

Sea x₁ = 2Ax + By + D
y g = mcd(4AC - B², 2AE - BD).

Multiplicando por 4AC - B² / g :

4AC - B² / g x₁² + (4AC - B²)² / g y² + 2(4AC - B²) (2AE - BD) / g y + (4AC - B²) (4AF - D²) / g = 0

4AC - B² / g x₁² + g y₁² + (4AC - B²) (4AF - D²) - (2AE - BD)² / g = 0

4AC - B² / g x₁² + g y₁² + 4A(4ACF - AE² - B²F + BDE - CD²) / g = 0

donde:

y₁ = 4AC - B² / g y + 2AE - BD / g

Hallar recurrencias entre las soluciones de la ecuación cuadrática general

X_n+1 = P X_n + Q Y_n + K
Y_n+1 = R X_n + S Y_n + L

Reemplazando en la ecuación original x por Px + Qy + K e y por Rx + Sy + L:

A(Px + Qy + K)² + B(Px + Qy + K) (Rx + Sy + L) + C(Rx + Sy + L)² + D(Px + Qy + K) + E(Rx + Sy + L) + F = 0

(AP² + BPR + CR²)x² + (2APQ + B(PS+QR) + 2CRS)xy + (AQ² + BQS + CS²)y² + (2AKP + B(KR+LP) + 2CLR + DP + ER)x + (2AKQ + B(KS+LQ) + 2CLS + DQ + ES)y + (AK² + BKL + CL² + DK + EL + F) = 0    (29)

Ahora investigaremos los valores dentro de los paréntesis.

• De (24) y (26):

  AP² + BPR + CR² = Ar² + BrAs + CA²s² = A(r² + Brs + ACs²)

  De la ecuación (28):

  AP² + BPR + CR² = A    (30)

• De (24) a (27):

  2APQ + B(PS+QR) + 2CRS = 2Ar(-Cs) + B[r(r+Bs)+(-Cs)As] + 2CAs(r+Bs) = -2ACrs + B(r²+Bs-ACs²) + 2ACrs + 2ABCs² = B(r²+Bs+ACs²)

  De la ecuación (28):

  2APQ + B(PS+QR) + 2CRS = B    (31)

• De (25) y (27):

  AQ² + BQS + CS² = AC²s² + B(-Cs)(r+Bs) + C(r+Bs)² = AC²s² - BCrs - B²Cs² + Cr² + 2BCrs + B²Cs² = AC² + BCrs + Cr² = C(r² + Brs + ACs²)

  De la ecuación (28):

  AQ² + BQS + CS² = C    (32)

Esto significa que 2AKP + B(KR+LP) + 2CLR + DP + ER = D y 2AKQ + B(KS+LQ) + 2CLS + DQ + ES = E.

Estas dos ecuaciones equivalen a:

(2AP+BR)K + (BP+2CR)L = -D(P-1) - ER
y (2AQ+BS)K + (BQ+2CS)L = -DQ - E(S-1)

Resolviendo el sistema de ecuaciones en K y L:

K = D[BQ - 2C(PS-QR-S)] + E[B(PS-RQ-P) - 2CR] / 4AC (PS - QR) + B² (QR - PS)

L = D[B(PS-RQ-S) - 2AQ] + E[BR - 2A(PS-RQ-P)] / 4AC (PS - QR) + B² (QR - PS)

Como PS - QR = r(r+Bs) - (-Cs)As = r² + Brs + ACs² = 1, estas ecuaciones se pueden simplificar a:

Ahora debemos mostrar que la expresión dentro del paréntesis derecho de (29) es igual a F. Esto significa que tenemos que probar que los valores de K y L recién hallados verifican la ecuación Z = AK² + BKL + CL² + DK + EL = 0    (33).

El desarrollo es muy complicado y no se reproducirá aquí, pero afortunadamente es múltiplo de 4AC-B², así que se cancela el cuadrado en el denominador, que es (4AC-B²)².

Esto significa que Z(4AC-B²) es un número entero e igual a:

AD²Q² - 2ADEPQ + AE²P² - AE² + BD²QS - BDEPS - BDEQR + BDE + BE²PR + CD²S² - CD² - 2CDERS + CE²R²

Reordenando términos:

AD²Q² + BD²QS + CD²S² - CD² - 2ADEPQ - BDEPS - BDEQR - 2CDERS + BDE + AE²P² + BE²PR + CE²R² - AE²

D²(AQ² + BQS + CS²) - CD² - DE(2APQ + BPS + BQR + 2CRS) + BDE + E²(AP² + BPR + CR²) - AE²

De (30), (31) y (32):

Z(4AC-B²) = CD² - CD² - BDE + BDE + AE² - AE² = 0

Esto significa que Z = 0, así que (33) se cumple, luego (29) se cumple también.

Sea K = K_DD + K_EE / 4AC - B² y L = L_DD + L_EE / 4AC - B²     (34)

Para continuar simplificando las expresiones debemos notar lo siguiente:

K_D = BQ - 2C(1 - S)
K_D = B(-Cs) - 2C(1 - r - Bs)
K_D = -BCs - 2C + 2Cr + 2BCs
K_D = C(-2 + 2r + Bs)    (35)
K_D = C(P + S - 2)

L_E = BR - 2A(1 - P)
L_E = ABs - 2A + 2Ar
L_E = A(-2 + 2r + Bs)
L_E = A(P + S - 2)

K_E = B(1 - P) - 2CR
K_E = B(1 - r) - 2ACs
K_E = B - Br - 2ACs    (36)

L_D = B(1 - S) - 2AQ
L_D = B(1 - r - Bs) + 2ACs
L_D = B - Br - B²s + 2ACs

L_D - K_E = (4AC - B²)s    (37)

Así que:

Generalmente los numeradores no serán múltiplos de 4AC - B², así que usando esta fórmula no podremos hallar una recurrencia para todos los valores de D y E.

Para algunos valores de D y E habrá soluciones, como se muestra a continuación. Usando las ecuaciones (24) - (27):

K_DL_E - K_EL_D = 4ACr² + 4ABCrs + 4A²C²s² - B²r² - B³rs - AB²Cs² - 4ABCs - B³s + 4AC - B² - 8ACr + 2B²r =

= (4AC - B²) (r² + Brs + ACs²) - (4AC - B²)Bs + (4AC - B²) - (4AC - B²)2r =

= (4AC - B²) (2 - 2r - Bs)

Los signos igual que figuran a continuación indican congruencia mod 4AC - B².

K_DL_E - K_EL_D = 0 => K_D/K_E = L_D/L_E    (38)

Como K y L deben ser enteros, de (34):

K_DD + K_EE = 0 => E = (-K_D/K_E)D    (39)

L_DD + L_EE = 0 => E = (-L_D/L_E)D

Estas ecuaciones son consistentes debido a la ecuación (38).

En algunos casos (véase ejemplo 6) podemos hallar una recurrencia utilizando las soluciones -r y -s ya que (-r)² + B(-r)(-s) + AC(-s)² = r² + Brs + ACs² = 1.

Si no se encuentran soluciones (como en el ejemplo 7), debemos usar el siguiente par de soluciones (r₁, s₁) de r² + Brs + ACs² = 1 porque en este caso siempre se podrán hallar soluciones como se muestra a continuación.

Primero debemos hallar r₁ y s₁ de r y s. Para hacerlo usaremos las fórmulas (24) - (28).

r₁ = r r + (-ACs)s = r² - ACs²
s₁ = s r + (r + Bs)s = 2rs + Bs²

Ahora reemplazaremos los valores de r y s por r₁ y s₁.

De (24): P₁ = r₁ = r² - ACs²
De (25): Q₁ = -Cs₁ = -C(2rs + Bs²)
De (26): R₁ = As₁ = A(2rs + Bs²)
De (27): S₁ = r₁ + Bs₁ = r² + 2Brs + (B² - AC)s²

De (35):

K_1D = C(-2 + 2r₁ + Bs₁)
K_1D = C[-2 + 2(r² - ACs²) + B(2rs + Bs²)]
K_1D = C[-2 + 2(r² + Brs + ACs²) - 4ACs² + B²s²]
K_1D = C[-2 + 2 + (B² - 4AC)s²]
K_1D = (B² - 4AC)Cs²

De (36):

K_1E = B - Br₁ - 2ACs₁
K_1E = B - Br² + ABCr² - 4ACrs - 2ABCr²
K_1E = B - B(r² + ACs²) - 4ACrs
K_1E = B - B(r² + ACs² + Brs - Brs) - 4ACrs
K_1E = B - B(1 - Brs) - 4ACrs
K_1E = (B² - 4AC)rs

De (37):

L_1D - K_1E = (4AC - B²)s₁
L_1D = (B² - 4AC) (rs - 2rs - Bs²)
L_1D = (B² - 4AC) (-rs - Bs²)

Por lo tanto:

K₁ = K_1DD + K_1EE / 4AC - B² = -CDs² - Ers

L₁ = L_1DD + L_1EE / 4AC - B² = Ds(r + Bs) - AEs²

Así, finalmente:

Nótese que en este caso, para hallar las soluciones usando el método de las fracciones continuas, debemos calcular dos períodos completos si la longitud del período es par y cuatro si es impar.

Ejemplo 6: 3x² + 13xy + 5y² + Dx + Ey + F = 0

La primera solución de r² + Brs + ACs² = r² + 13 rs + 15 s² = 1 usando el método de la fracción continua es r = -8351 y s = 6525.

P = r = -8351
Q = -Cs = -32625
R = As = 19575
S = r + Bs = 76474

K = CD(P+S-2) + E(B-Br-2ACs) / 4AC-B² = -340605 / 109 D + 87174 / 109 E

L = D(B-Br-2ACs) + AE(P+S-2) / 4AC-B² + Ds = 798399 / 109 D - 204363 / 109 E

El numerador de K (o L) no es múltiplo del denominador (4AC - B² = -109), así que no hay recurrencia con los valores de P, Q, R, S mostrados arriba, excepto para casos especiales (de acuerdo a (39), cuando E ≡ 93 D (mod 109)).

Usando la solución r = 8351, s = -6525 obtenemos:

P = r = 8351
Q = -Cs = 32625
R = As = -19575
S = r + Bs = -76474

K = CD(P+S-2) + E(B-Br-2ACs) / 4AC-B² = 3125 D - 800 E

L = D(B-Br-2ACs) + AE(P+S-2) / 4AC-B² + Ds = -7325 D + 1875 E

Así que la recurrencia entre soluciones es:

Verificación: Sabiendo que x = 2, y = 3 es una solución de 3x² + 13xy + 5y² - 11x - 7y - 92 = 0, encontrar otras dos soluciones.

Reemplazando D = -11 y E = -7 en las ecuaciones anteriores:

X_n+1 = 8351 X_n - 32625 Y_n - 28775
Y_n+1 = -19575 X_n + 76474 Y_n + 67450

Así que reemplazando aquí X₀ = 2 e Y₀ = 3, hallamos X₁ = 85802 e Y₁ = -201122.

y reemplazando X₁ = 85802 e Y₁ = -201122, hallamos X₂ = -5845 101523 e Y₂ = 13701 097128.

Reemplazando estos valores en la ecuación original podemos verificar que estos valores son correctos.

Ejemplo 7: 3x² + 14xy + 6y² + Dx + Ey + F = 0

La primera solución de r² + Brs + ACs² = r² + 14 rs + 18 s² = 1 usando el método de la fracción continua es r = -391 y s = 273.

P = r = -391
Q = -Cs = -1638
R = As = 819
S = r + Bs = 3431

K = CD(P+S-2) + E(B-Br-2ACs) / 4AC-B² = -147 D + 35 E

L = D(B-Br-2ACs) + AE(P+S-2) / 4AC-B² + Ds = 308 D - 147 / 2 E

El numerador de L no es múltiplo del denominador (4AC - B² = -124), así que no hay recurrencia con los valores de P, Q, R, S mostrados arriba, excepto para casos especiales (cuando E es par).

Usando la solución r = 391, s = -273 obtenemos:

P = r = 391
Q = -Cs = 1638
R = As = -819
S = r + Bs = -3431

K = CD(P+S-2) + E(B-Br-2ACs) / 4AC-B² = -4563 / 31 D - 1092 / 31 E

L = D(B-Br-2ACs) + AE(P+S-2) / 4AC-B² + Ds = 4563 / 62 D - 9555 / 31 E

El numerador de K (o L) no es múltiplo del denominador (4AC - B² = -124), así que no hay recurrencia con los valores de P, Q, R, S mostrados arriba, excepto para casos especiales.

Usando (40) y (41):

P₁ = r² - ACs² = -1188641
Q₁ = -Cs(2r+Bs) = -4979520
R₁ = As(2r+Bs) = 2489760
S₁ = r² + 2Brs + (B²-AC)s² = 10430239
K₁ = -CDs² - Ers = -106743 D + 447174 E
L₁ = Ds(r+Bs) - AEs² = 936663 D - 223587 E

Así que la recurrencia entre soluciones es:

Verificación: Sabiendo que x = 4, y = 7 es una solución de 3x² + 14xy + 6y² - 17x - 23y - 505 = 0, hallar otras dos soluciones.

Reemplazando D = -17 y E = -23 en las ecuaciones previas:

X_n+1 = -1188641 X_n - 4979520 Y_n + 5146869

Y_n+1 = 2489760 X_n + 10430239 Y_n - 10780770

Así que reemplazando aquí X₀ = 4 e Y₀ = 7, hallamos X₁ = -34 464335 e Y₁ = 72 189943.

y reemplazando X₁ = -34 464335 e Y₁ = 72 189943, hallamos X₂ = -318 505538 201756 e Y₂ = 667 150425 396007.

Reemplazando estos valores en la ecuación original podemos verificar que estos valores son correctos.

Programas que usan estos métodos

Escribí un programa que usa estos métodos:

Siga el enlace para correr un programa Java compatible con Internet Explorer y Firefox.

El programa funciona en dos modos: sólo solución y paso a paso. En este modo, el programa muestra cómo se hallan los resultados.

Formulario para enviarme sus comentarios.

Última modificación: 2 de mayo de 2016.