Métodos para resolver Ax2 + Bxy + Cy2 + Dx + Ey + F = 0

por Dario Alejandro Alpern

El propósito de este artículo es mostrar cómo resolver la ecuación diofántica Ax2 + Bxy + Cy2 + 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 4y2 - 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

La ecuación es ahora: Dx + Ey + F = 0. Se pueden distinguir varios casos:

Ejemplo 1: Resolver 10x + 84y + 16 = 0.

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:

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:

x = -136 + 42 t
y = 16 - 5 t

donde t es cualquier número entero.


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

Como A = C = 0 la ecuación original se reduce a Bxy + Dx + Ey + F = 0, así que:

Bxy + Dx + Ey + F=0
Bxy + Dx + Ey=-F
B2xy + BDx + BEy=-BF
B2xy + BDx + BEy + DE=DE - BF
(Bx + E) (By + D)=DE - BF

Por lo tanto los valores de x e y se pueden hallar a partir de los divisores de DE - BF. Sean d1, d2, ..., dn todos los divisores de DE - BF. Así,

Bx + E=di     By + D=(DE - BF) / di
Bx=di - E     By=(DE - BF) / di - D
x=di - E
B
y=(DE - BF) / di - D
B

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:

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


Caso elíptico B2 - 4AC < 0

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

Operando con la ecuación cuadrática original:

Ax2 + Bxy + Cy2 + Dx + Ey + F = 0

Cy2 + (Bx + E)y + (Ax2 + Dx + F) = 0

y =-(Bx + E) ± sqrt[(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)2 - 4C(Ax2 + Dx + F) = 0

(B2 - 4AC)x2 + 2(BE - 2CD)x + (E2 - 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 42x2 + 8xy + 15y2 + 23x + 17y - 4915 = 0.

Como B2 - 4AC = 82 - 4*42*15 = -2456 < 0 la ecución es elíptica.

Los valores de x deberán estar entre las raíces de (B2 - 4AC)x2 + 2(BE - 2CD)x + (E2 - 4CF) = ­2456x2 - 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 B2 - 4AC = 0

Sean g = mcd(A,C), a = A/g >= 0, b = B/g, c = C/g >= 0.

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

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

Multiplicando la ecuación original por sqrt a:

sqrt ag(ax2 + bxy + cy2) + sqrt aDx + sqrt aEy + sqrt aF = 0

sqrt ag(sqrt ax + sqrt cy)2 + sqrt aDx + sqrt aEy + sqrt aF = 0

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

Sumando y restando sqrt cDy:

sqrt ag(sqrt ax + sqrt cy)2 + D(sqrt ax + sqrt cy) - sqrt cDy + sqrt aEy + sqrt aF = 0

Sea u = sqrt ax + sqrt cy:    (i)

sqrt agu2 + Du + (sqrt aE - sqrt cD)y + sqrt aF = 0

(sqrt cD - sqrt aE)y = sqrt agu2 + Du + sqrt aF (ii)

Existen dos casos: sqrt cD - sqrt aE = 0 (dos rectas paralelas) o sqrt cD - sqrt aE != 0 (una parábola).

En el primer caso, sqrt cD - sqrt aE = 0.

De (ii): sqrt agu2 + Du + sqrt aF = 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 u1 y u2 las raíces de la ecuación.

De (i) resulta: sqrt ax + sqrt cy - u1 = 0 y sqrt ax + sqrt cy - u2 = 0 que se pueden resolver con los métodos explicados para la ecuación lineal.

En el segundo caso, sqrt agu2 + Du + sqrt aF deberá ser múltiplo de sqrt cD - sqrt aE.

Sean u0, u1,... los valores de u en el rango 0 <= u < |sqrt cD - sqrt aE| en los cuales se cumple la condición anterior.

Así u = ui + (sqrt cD - sqrt aE)t, donde t es cualquier número entero.   (iii)

Reemplazando (iii) en (ii):

(sqrt cD - sqrt aE)y = sqrt ag[ui + (sqrt cD - sqrt aE)t]2 + D[ui + (sqrt cD - sqrt aE)t] + sqrt aF

y = sqrt ag(sqrt cD - sqrt aE)t2 + (D + 2sqrt agui)t + sqrt agui2 + Dui + sqrt aF
sqrt cD - sqrt aE

De (i) y (iii):

u = sqrt ax + sqrt cy = ui + (sqrt cD - sqrt aE)t

sqrt ax=sqrt asqrt cg(sqrt aE - sqrt cD)t2 + (sqrt cD - sqrt aE - 2sqrt asqrt cgui - sqrt cD)t +
+
ui - sqrt csqrt agui2 + Dui + sqrt aF
sqrt cD - sqrt aE

sqrt ax=sqrt asqrt cg(sqrt aE - sqrt cD)t2 + (- sqrt aE - 2sqrt asqrt cgui)t +
+
ui(sqrt cD - sqrt aE) - sqrt asqrt cgui2 - sqrt cDui - sqrt asqrt cF
sqrt cD - sqrt aE

sqrt ax=sqrt asqrt cg(sqrt aE - sqrt cD)t2 + (- sqrt aE - 2sqrt asqrt cgui)t -
-
sqrt asqrt cgui2 + sqrt aEui + sqrt asqrt cF
sqrt cD - sqrt aE

x = sqrt cg(sqrt aE - sqrt cD)t2 - (E + 2sqrt cgui)t - sqrt cgui2 + Eui + sqrt cF
sqrt cD - sqrt aE

y = sqrt ag(sqrt cD - sqrt aE)t2 + (D + 2sqrt agui)t + sqrt agui2 + Dui + sqrt aF
sqrt cD - sqrt aE

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

Debemos calcular los valores de g, a, c, sqrt a, sqrt c, sqrt cD - sqrt aE y sqrt agu2 + Du + sqrt aF.

g = mcd(8, 18) = 2
a = 8/2 = 4
c = 18/2 = 9
sqrt a = 2
sqrt c = -3 (ya que B/A = -24/8 < 0)
sqrt cD - sqrt aE = -3 * 5 - 2 * 7 = -29 (segundo caso)
sqrt agu2 + Du + sqrt aF = 4u2 + 5u + 32

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

Los valores de u son: u0 = 2 y u1 = 4.

Para u0 = 2:

x = -174 t2 - 17 t - 2
y = -116 t2 - 21 t - 2

Para u0 = 4:

x = -174 t2 - 41 t - 4
y = -116 t2 - 37 t - 4


Caso hiperbólico B2 - 4AC > 0

Contenido


Hallar soluciones de la ecuación homogénea Ax2 + Bxy + Cy2 + F = 0

Si F = 0 tenemos la solución trivial x = 0 e y = 0. Ahora investigaremos si hay más soluciones.

Ax2 + Bxy + Cy2 = 0

Multiplicando by 4A:
4A2x2 + 4ABxy + 4ACy2 = -4AF
4A2x2 + 4ABxy + B2y2 - B2y2 + 4ACy2 = -4AF
(2Ax + By)2 - (B2 - 4AC)y2 = -4AF

Esto se puede interpretar como una diferencia de cuadrados:

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

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

Para hallar las soluciones en este caso se puede utilizar el método para 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 B2 - 4AC = k2 para algún entero k, los paréntesis en la ecuación anterior deben ser factores de -4AF.

Sean u1, u2,... los divisores positivos y negativos de -4AF.

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

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

Por lo tanto:

y = (ui + 4AF/ui) / (2k)
x = (ui - (B+k)y) / (2A)

Debemos descartar los valores de ui que hagan x ó y no enteros.


Consideraremos ahora el caso F != 0 y B2 - 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 F2 < B2 - 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 At2 + Bt + C = 0.

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

Por otra parte, si 4 F2 >= B2 - 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: AG2u2 + BG2uv + CG2v2 + F = 0, así que F será múltiplo de G2.

Dividiendo la ecuación por G2:

Au2 + Buv + Cv2 + F/G2 = 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)2 + B(sy - Fz)y + Cy2 + F = 0

As2y2 - 2AFsyz + AF2z2 + Bsy2 - BFyz + Cy2 = -F

(As2 + Bs + C) y2 + (-2As - B)Fyz + AF2z2 = - F

Dividiendo por -F:

-(As2 + Bs + C) y2 / F + (2As + B)yz - AFz2 = 1    (3)

Ahora debemos determinar los valores de s entre 0 y F - 1 tales que As2 + 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 -(As2 + Bs + C) t2 / 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) = 1debemos hacer la sustitución y = sx - Fz    (4). Reemplazando en la ecuación original:

Ax2 + Bx(sx - Fz) + C(sx - Fz)2 + F = 0

Ax2 + Bsx2 - BFxz + Cs2x2 - 2CFsxz + CF2z2 = -F

(Cs2 + Bs + A) x2 + (-2Cs - B)Fxz + CF2z2 = - F

Dividiendo por -F:

-(Cs2 + Bs + A) x2 / F + (2Cs + B)xz - CFz2 = 1    (5).

Ahora debemos determinar los valores de s entre 0 y F - 1 tales que Cs2 + 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 -(Cs2 + Bs + A) t2 / 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 y y = mX + nY    (7) obtenemos X = nx - jy y 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.

Ax2 + Bxy + Cy2 =
= A(iX+jY)2 + B(iX+jY)(mX+nY) + C(mX+nY)2 =
= aX2 + bXY + cY2

donde:

a = Ai2 + Bim + Cm2    (9)
b = 2Aij + Bin + Bjm + 2Cmn    (10)
c = Aj2 + Bjn + Cn2    (11)

Debemos hallar los valores de i y m tales que a = Ai2 + Bim + Cm2 sea relativamente primo a F.

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

Como mcd(A, F) > 1 resulta mcd(Ai2 + Bim + Cm2, 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):

ABCi, mEjemplos
A = 0B = 0C = 0No se aplica (mcd(A, B, C) = 1)
A = 0B = 0C != 0m != 0i = 0, m = 1
A = 0B != 0C = 0i != 0, m != 0i = 1, m = 1
A = 0B != 0C != 0m != 0, i != -Cm/Bi = 1-C, m = B
A != 0B = 0C = 0i != 0i = 1, m = 0
A != 0B = 0C != 0i != 0 ó m != 0i = 1, m = 1
A != 0B != 0C = 0i != 0, m != -Ai/Bi = B, m = 1-A
A != 0B != 0C != 0i != 0 ó m != 0i = 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 par apoder hallar ambos valores:

    para i=0 a |F|-1
       para m=0 a i+1
          si mcd(i, m) = 1 y mcd(Ai2 + Bim + Cm2, F) = 1, fin.
       siguiente m
    siguiente 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 e-mail. Yo introduje algunos cambios.

Ejemplo 5: Encontrar algunas soluciones de 18 x2 + 41 xy + 19 y2 - 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 x2 + 41 xy + 19 y2 - 24 = 0

Debemos hallar el desarrollo en fracción continua de las raíces de 18 t2 + 41 t + 19 = 0, esto es, (sqrt(313) - 41) /36

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

Como 4f2 >= b2 - 4ac, no se encontrarán soluciones utilizando el desarrollo arriba indicado.

Sea x = sy - fz, así [-(as2 + bs + c)/f]y2 + (2sa + b)yz - afz2 = 1.

Por lo que 18 s2 + 41 s + 19 debe ser múltiplo de 24.

Esto es válido para s = 19.

Como 2 * 2 es un divisor del coeficiente independiente (-24), las soluciones deben ser 2 veces las soluciones de 18 u2 + 41 uv + 19 v2 - 6 = 0.

Debemos hallar el desarrollo en fracción continua de las raíces de 18 t2 + 41 t + 19 = 0, esto es, (sqrt(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 U0 y V0 (en la tercera columna se encuentran los valores de 18 u2 + 41 uv + 19 v2):

cnunvn
 10
-1-11-4
2-1212
1-23-3
5-11172
8-90139-11
1-1011566
2-292451-1
17-506578236
2-1042216097-11
1-15487239202
8-134318207457-3
5-6870771 06120512
1-8213951 268662-4
3-3 1512624 8671919
1-3 9726576 135853-8
1-7 12391911 0030446
2-18 22049528 141941-6
2-43 56490967 2869268
1-61 78540495 428867-9
1-105 350313162 7157934
3-377 836343583 576246-12
1-483 186656746 2920393
5-2793 7696234315 036441-2
8-22833 34364035266 58356711
1-25627 11326339581 620008-6
2-74087 570166114429 8235831
17-1 285115 8060851 984888 620919-6
2-2 644319 1823364 084207 06542111
1-3 929434 9884216 069095 686340-2
8-34 079799 08970452 636972 5561413
5-174 328430 436941269 253958 467045-12
1-208 408229 526645321 890931 0231864
3-799 553119 0168761234 926751 536603-9
1-1007 961348 5435211556 817682 5597898
1-1807 514467 5603972791 744434 096392-6
2-4622 990283 6643157140 306550 7525736
2-11053 495034 88902717072 357535 601538-8
1-15676 485318 55334224212 664086 3541119
1-26729 980353 44236941285 021621 955649-4
3-95866 426378 880449148067 728952 22105812

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

X0 = -202
Y0 = 312

X0 = 202
Y0 = -312

X0 = -10130
Y0 = 15646

X0 = 10130
Y0 = -15646

X0 = -14 247838 (8 dígitos)
Y0 = 22 006088 (8 dígitos)

X0 = 14 247838 (8 dígitos)
Y0 = -22 006088 (8 dígitos)

X0 = -9245 980567 328630 (16 dígitos)
Y0 = 14280 613101 505146 (17 dígitos)

X0 = 9245 980567 328630 (16 dígitos)
Y0 = -14280 613101 505146 (17 dígitos)

La otra raíz de la ecuación 18 t2 + 41 t + 19 = 0 es (-sqrt(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 U0 y V0 (en la tercera columna se encuentran los valores de 18 u2 + 41 uv + 19 v2):

cnunvn
 10
-2-219
2-32-8
1-536
2-138-6
2-31198
1-4427-9
1-75464
3-269165-12
1-3442113
5-19891220-2
8-16256997111
1-1824511191-6
2-52746323531
17-914927561192-6
2-1 8826001 15473711
1-2 7975271 715929-2
8-24 26281614 8821693
5-124 11160776 126774-12
1-148 37442391 0089434
3-569 234876349 153603-9
1-717 609299440 1625468
1-1286 844175789 316149-6
2-3291 2976492018 7948446
2-7869 4394734826 905837-8
1-11160 7371226845 7006819
1-19030 17659511672 606518-4
3-68251 26690741863 52023512
1-87281 44350253536 126753-3
5-504658 484417309544 1540002
8-4 124549 3188382 529889 358753-11
1-4 629207 8032552 839433 5127536
2-13 382964 9253488 208756 384259-1
17-232 139611 534171142 388292 0451566
2-477 662187 993690292 985340 474571-11
1-709 801799 527861435 373632 5197272
8-6156 076584 2165783775 974400 632387-3
5-31490 184720 61075119315 245635 68166212
1-37646 261304 82732923091 220036 314049-4
3-144428 968635 09273888588 905744 6238099
1-182075 229939 920067111680 125780 937858-8

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

X0 = 10
Y0 = -6

X0 = -10
Y0 = 6

X0 = 6582 595298 (10 dígitos)
Y0 = -4037 589688 (10 dígitos)

X0 = -6582 595298 (10 dígitos)
Y0 = 4037 589688 (10 dígitos)

X0 = 9 258415 606510 (13 dígitos)
Y0 = -5 678867 025506 (13 dígitos)

X0 = -9 258415 606510 (13 dígitos)
Y0 = 5 678867 025506 (13 dígitos)

X0 = 464 279223 068342 (15 dígitos)
Y0 = -284 776584 090312 (15 dígitos)

X0 = -464 279223 068342 (15 dígitos)
Y0 = 284 776584 090312 (15 dígitos)


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

Ahora que se encontraron algunas soluciones de la ecuación original, hallaremos otras soluciones, de hecho, una familia de infinitas soluciones, donde:

Xn+1 = P Xn + Q Yn
Yn+1 = R Xn + S Yn

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

Sea M(x, y) = Ax2 + Bxy + Cy2 = M y N(u, v) = u2 + Buv + ACv2 = N.

M(p, q) = Ap2 + Bpq + Cq2

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

M(p, q)/A = p2 + Dpq + Eq2

M(p/q, 1)/A = (p/q)2 + 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 + sqrt(B2 - 4AC)
2A
   y   J' =-B - sqrt(B2 - 4AC)
2A

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

J2 = -DJ - E    (14)
J'2 = -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 + sqrt(B2 - 4AC)
2
   y   K' =-B - sqrt(B2 - 4AC)
2

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 + AJ2qs)

De (14) obtenemos:

[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'2qs)

De (15) obtenemos:

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

Let 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') = X2 - (J + J')XY + JJ'Y2

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

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

AX2 + BXY + CY2 = 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) = r2 + Brs + ACs2 = 1,
Xn = p, Yn = q, Xn+1 = X e Yn+1 = Y (ya que los dos últimos pares de números son soluciones de la ecuación original).

De (23) obtenemos:

Xn+1 = rXn - CsYn+1
Yn+1 = AsXn + rYn+1 + BsYn+1

Esto significa que:

Xn+1 = P Xn + Q Yn
Yn+1 = R Xn + S Yn
P = r    (24)
Q = -Cs    (25)
R = As    (26)
S = r + Bs    (27)
donde
r2 + Brs + ACs2 = 1    (28)

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


Hallar soluciones de la ecuación cuadrática general

Ax2 + Bxy + Cy2 + Dx + Ey + F = 0

Multiplicando la ecuación por 4A:

4A2x2 + 4ABxy + 4ACy2 + 4ADx + 4AEy + 4AF = 0
(2Ax + By + D)2 - (By + D)2 + 4ACy2 + 4AEy + 4AF = 0
(2Ax + By + D)2 + (4AC - B2)y2 + (4AE - 2BD)y + (4AF - D2) = 0

Sea x1 = 2Ax + By + D
y g = mcd(4AC - B2, 2AE - BD).

Multiplicando por (4AC - B2)/g:

4AC - B2
g
x12 +(4AC - B2)2
g
y2 +2(4AC - B2) (2AE - BD)
g
y +(4AC - B2) (4AF - D2)
g
= 0

4AC - B2
g
x12 + g y12 +(4AC - B2) (4AF - D2) - (2AE - BD)2
g
= 0

4AC - B2
g
x12 + g y12 +4A(4ACF - AE2 - B2F + BDE - CD2)
g
= 0

donde:

y1 =4AC - B2
g
y + 2AE - BD
g


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

Ahora asumiremos que las soluciones tendrán la forma:

Xn+1 = P Xn + Q Yn + K
Yn+1 = R Xn + S Yn + L

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

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

(AP2 + BPR + CR2)x2 + (2APQ + B(PS+QR) + 2CRS)xy + (AQ2 + BQS + CS2)y2 + (2AKP + B(KR+LP) + 2CLR + DP + ER)x + (2AKQ + B(KS+LQ) + 2CLS + DQ + ES)y + (AK2 + BKL + CL2 + DK + EL + F) = 0    (29)

Ahora investigaremos los valores dentro de los paréntesis.

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) + B2 (QR - PS)

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

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

K =D[BQ - 2C(1-S)] + E[B(1-P) - 2CR]
4AC - B2

L =D[B(1-S) - 2AQ] + E[BR - 2A(1-P)]
4AC - B2

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 = AK2 + BKL + CL2 + DK + EL = 0    (33).

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

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

AD2Q2 - 2ADEPQ + AE2P2 - AE2 + BD2QS - BDEPS - BDEQR + BDE + BE2PR + CD2S2 - CD2 - 2CDERS + CE2R2

Reordenando términos:

AD2Q2 + BD2QS + CD2S2 - CD2 - 2ADEPQ - BDEPS - BDEQR - 2CDERS + BDE + AE2P2 + BE2PR + CE2R2 - AE2

D2(AQ2 + BQS + CS2) - CD2 - DE(2APQ + BPS + BQR + 2CRS) + BDE + E2(AP2 + BPR + CR2) - AE2

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

Z(4AC-B2) = CD2 - CD2 - BDE + BDE + AE2 - AE2 = 0

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

Sea K =KDD + KEE
4AC - B2
   y   L =LDD + LEE
4AC - B2
    (34)

Para continuar simplificando las expresiones debemos notar lo siguiente:

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

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

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

LD = B(1 - S) - 2AQ
LD = B(1 - r - Bs) + 2ACs
LD = B - Br - B2s + 2ACs

LD - KE = (4AC - B2)s    (37)

Así que:

K =CD(P+S-2) + E(B-Br-2ACs)
4AC - B2

L =D(B-Br-2ACs) + AE(P+S-2)
4AC - B2
+ Ds

Generalmente los numeradores no serán múltiplos de 4AC - B2, 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):

KDLE - KELD = 4ACr2 + 4ABCrs + 4A2C2s2 - B2r2 - B3rs - AB2Cs2 - 4ABCs - B3s + 4AC - B2 - 8ACr + 2B2r =

= (4AC - B2) (r2 + Brs + ACs2) - (4AC - B2)Bs + (4AC - B2) - (4AC - B2)2r =

= (4AC - B2) (2 - 2r - Bs)

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

KDLE - KELD = 0 => KD/KE = LD/LE    (38)

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

KDD + KEE = 0 => E = (-KD/KE)D    (39)

LDD + LEE = 0 => E = (-LD/LE)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)2 + B(-r)(-s) + AC(-s)2 = r2 + Brs + ACs2 = 1.

Si no se encuentran soluciones (como en el ejemplo 7), debemos usar el siguiente par de soluciones (r1, s1) de r2 + Brs + ACs2 = 1 porque en este caso siempre se podrán hallar soluciones como se muestra a continuación.

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

r1 = r r + (-ACs)s = r2 - ACs2
s1 = s r + (r + Bs)s = 2rs + Bs2

Ahora reemplazaremos los valores de r y s por r1 y s1.

De (24): P1 = r1 = r2 - ACs2
De (25): Q1 = -Cs1 = -C(2rs + Bs2)
De (26): R1 = As1 = A(2rs + Bs2)
De (27): S1 = r1 + Bs1 = r2 + 2Brs + (B2 - AC)s2

De (35):

K1D = C(-2 + 2r1 + Bs1)
K1D = C[-2 + 2(r2 - ACs2) + B(2rs + Bs2)]
K1D = C[-2 + 2(r2 + Brs + ACs2) - 4ACs2 + B2s2]
K1D = C[-2 + 2 + (B2 - 4AC)s2]
K1D = (B2 - 4AC)Cs2

De (36):

K1E = B - Br1 - 2ACs1
K1E = B - Br2 + ABCr2 - 4ACrs - 2ABCr2
K1E = B - B(r2 + ACs2) - 4ACrs
K1E = B - B(r2 + ACs2 + Brs - Brs) - 4ACrs
K1E = B - B(1 - Brs) - 4ACrs
K1E = (B2 - 4AC)rs

De (37):

L1D - K1E = (4AC - B2)s1
L1D = (B2 - 4AC) (rs - 2rs - Bs2)
L1D = (B2 - 4AC) (-rs - Bs2)

Por lo tanto:

K1 =K1DD + K1EE
4AC - B2
= -CDs2 - Ers

L1 =L1DD + L1EE
4AC - B2
= Ds(r + Bs) - AEs2

Así que, finalmente:

Xn+1 = (r2 - ACs2)Xn - Cs(2r+Bs)Yn - CDs2 - Ers    (40)

Yn+1 = As(2r+Bs)Xn + [r2 + 2Brs + (B2-AC)s2]Yn + Ds(r+Bs) - AEs2    (41)

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: 3x2 + 13xy + 5y2 + Dx + Ey + F = 0

La primera solución de r2 + Brs + ACs2 = r2 + 13 rs + 15 s2 = 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-B2
=-340605
109
D +87174
109
E

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

El numerador de K (o L) no es múltiplo del denominador (4AC - B2 = -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-B2
=3125 D - 800 E

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

Así que la recurrencia entre soluciones es:

Xn+1 = 8351 Xn - 32625 Yn + (3125 D - 800 E)

Yn+1 = -19575 Xn - 76474 Yn + (-7325 D + 1875 E)

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

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

Xn+1 = 8351 Xn - 32625 Yn - 28775
Yn+1 = -19575 Xn + 76474 Yn + 67450

Así que reemplazando aquí X0 = 2 e Y0 = 3, hallamos X1 = 85802 e Y1 = -201122.

y reemplazando X1 = 85802 e Y1 = -201122, hallamos X2 = -5845 101523 e Y2 = 13701 097128.

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

Ejemplo 7: 3x2 + 14xy + 6y2 + Dx + Ey + F = 0

La primera solución de r2 + Brs + ACs2 = r2 + 14 rs + 18 s2 = 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-B2
=-147 D + 35 E

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

El numerador de L no es múltiplo del denominador (4AC - B2 = -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-B2
=-4563
31
D -1092
31
E

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

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

Usando (40) y (41):

P1 = r2 - ACs2 = -1188641
Q1 = -Cs(2r+Bs) = -4979520
R1 = As(2r+Bs) = 2489760
S1 = r2 + 2Brs + (B2-AC)s2 = 10430239
K1 = -CDs2 - Ers = -106743 D + 447174 E
L1 = Ds(r+Bs) - AEs2 = 936663 D - 223587 E

Así que la recurrencia entre soluciones es:

Xn+1 = -1188641 Xn - 4979520 Yn + (106743 D - 447174 E)

Yn+1 = 2489760 Xn + 10430239 Yn + (936663 D - 223587 E)

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

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

Xn+1 = -1188641 Xn - 4979520 Yn + 5146869

Yn+1 = 2489760 Xn + 10430239 Yn - 10780770

Así que reemplazando aquí X0 = 4 e Y0 = 7, hallamos X1 = -34 464335 e Y1 = 72 189943.

y reemplazando X1 = -34 464335 e Y1 = 72 189943, hallamos X2 = -318 505538 201756 e Y2 = 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í dos programas que usan estos métodos:

Apriete aquí para correr un programa en JavaScript compatible con Internet Explorer 3.0 o Netscape Navigator 3.0 o posteriores (sin terminar todavía).

Apriete aquí para correr un programa en Java compatible with Internet Explorer 4.0 o Netscape Navigator 4.0 o posterior. Es 50 veces más rápido que el otro programa (los textos se muestran en inglés).

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

Apriete aquí para enviarme sus comentarios.

Ultima modificación: 24 de agosto de 2007.