Resolver : $x^2-92 y^2=1$

Question

Como algunos de ustedes sabrán, esta es la ecuación de Brahmagupta. ¿Cómo encontrar la solución para esto? Me refiero a la solución integral? ¿Como resolverla usando programacion?

Intenté algo como $x^2=1+92y^2$

$x=\sqrt{1+92y^2}$

Utiliza el método de fuerza bruta para comprobar cada y ? ¿Hay alguna respuesta mejor?

Answer 1

Creo que la forma sistemática más común de resolver este tipo de problemas es utilizando fracciones continuas. Reitero la sugerencia de @Quimey de consultar Wikipedia para Ecuación de Pell y en concreto la sección "Solución fundamental mediante fracciones continuas" y la Papel Lenstra citado allí.

En este caso como fracción continua periódica $$ \sqrt{92} = [9;1,1,2,4,2,1,1,18,1,1,2\ldots] = 9+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{4+\cfrac{1}{2+\cdots}}}}} $$ y después de 7 términos obtenemos la aproximación $\sqrt{92}\simeq 1151/120$ que da la solución fundamental.

En cuanto a la aplicación de un algoritmo para encontrar la fracción continua para raíces cuadradas, usted debe ser capaz de encontrar recursos en línea con una búsqueda, pero puede empezar por echar un vistazo a esta pregunta .

Answer 2

En cuanto a la parte de programación, se me ocurrió poner algo sencillo de fuerza bruta en Python sólo como ejemplo.

# Start at (1, 1) because (1, 0) is a trivial solution
x, y = 1, 1
z = x**2 - 92*(y**2)

while z != 1:
    if z > 1:
        y += 1
    else:
        x += 1

    z = x**2 - 92*(y**2)

print x, y

Esto produce la primera solución

1151 120

Por supuesto, como solución de fuerza bruta este código no te llevará muy lejos si, por ejemplo, sustituyes 92 por números mayores (o incluso si lo sustituyes por 61, para el caso).

Answer 3

La clave es una (especie de) identidad milagrosa: $(x_1^2 - Ny_1^2)(x_2^2 - Ny_2^2)=(x_1x_2 + Ny_1y_2) - N(x_1y_2 + x_2y_1)^2$ .

Esto significa que si $x_1^2 - Ny_1^2 = k_1$ y $x_2 - Ny_2^2 = k_2$ entonces $(x_1x_2 + Ny_1y_2) - N(x_1y_2 + x_2y_1)^2 = k_1k_2$ .

Podemos reescribir esto de la siguiente manera: si $(x_1,y_1,k_1)$ y $(x_2,y_2,k_2)$ satisfacer $x^2-92y^2 = k$ entonces $(x_1x_2 + Ny_1y_2,x_1y_2 + x_2y_1, k_1k_2)$ también es una solución. Esta operación se llama "componer".

Ahora es obvio que $(10,1,8)$ es uno de esos triples que satisface $x^2 - 92y^2 = k$ . Podemos componer $(10,1,8)$ con $(10,1,8)$ para obtener el triple $(192, 20, 64)$ y dividir $x$ y $y$ por $8$ (para que $k$ se reduce en un factor de $64$ ), de modo que tenemos $(24, \frac{5}{2}, 1)$ . Componiendo esto consigo mismo de nuevo, tenemos la solución $(1151, 120, 1)$ .

Answer 4

def pr_sol(maxval,N,ee,ff):
    count=0
    aa,bb=0,1
    gg=N*ff
    while count<maxval:
        if bb**2 - 1 ==N*aa**2:
            print(bb,'^2-1=',N,'*',aa,'^2')
        else:
            print(bb,'^2+1=',N,'*',aa,'^2')
        anew=ee*aa+ff*bb
        bnew=gg*aa+ee*bb
        aa=anew
        bb=bnew
        count+=1
  return 

pr_sol(20,92,1151,120) #imprime las 20 primeras soluciones cuando N=92

""" la solución más pequeña es 1151,120 donde 1151 ^2-1= 92 * 120 ^2 (de wikipedia). (No estoy seguro si es lo mismo que la recursividad de wikipedia, pero en este caso se aplica la siguiente recursividad:

a_{t+1}=1151*a_{t} +120*b_{t}
b_{t+1}=120*92*a_{t} +1151*b_{t}
(in general you can generate such a recursion, which gives 
values for x^2-1=Ny^2  AND x^2+1=Ny^2 
(but x^2 ==91 mod 92 has no solutions so
there are no sol to x^2+1=Ny^2 ))

The first few solutions are:
1 ^2-1= 92 * 0 ^2  (a,b)=( 0 , 1 ) 
1151 ^2-1= 92 * 120 ^2 (a,b)=( 120 , 1151 )
2649601 ^2-1= 92 * 276240 ^2 (a,b)=( 276240 , 2649601 ) 
6099380351 ^2-1= 92 * 635904360 ^2 
14040770918401 ^2-1= 92 * 1463851560480 ^2 
32321848554778751 ^2-1= 92 * 3369785656320600 ^2
I've just been doing some investigation into these equations
and found this recursion. (which has some advantage. For 
example N=313 has very large first solution to x^2-1=Ny^2 but 
you can generate the numbers from the much smaller solution:
126862368^2 +1 =313 *  7170685^2
and the recursion: 
a_{t+1}= 126862368 a_t+7170685 b_t
b_{t+1}=313*7170685a_t+126862368  b_t
so 
pr_sol(20,313,126862368,7170685) 
prints first 20 solutions for N=313 
(note they alternate between x^2+1=313y^2 and x^2-1=313y^2)

"""