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

Question

As some of you might know,this is Brahmagupta's equation . How to find solution for this ? I mean integral solution? How to solve it using programming ?

I tried something like $x^2=1+92y^2$

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

Use brute force approach to check for every y ? Is there any better answer ?

Answer 1

As for the programming part, I thought I'd put up some simple brute force Python just as an example.

# 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

This outputs the first solution

1151 120

Of course, as a brute force solution this code won't get you very far if, for example, you replaced 92 with larger numbers (or even if you replaced it by 61, for that matter).

Answer 2

I think the most common systematic way to solve this type of problem is using continued fractions. I'll reiterate @Quimey's suggestion to refer to Wikipedia for Pell's Equation and specifically the section "Fundamental solution via continued fractions" and the Lenstra paper cited there.

In this case as a periodic continued fraction $$ \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}}}}} $$ and after 7 terms we get the approximation $\sqrt{92}\simeq 1151/120$ which gives the fundamental solution.

As for implementing an algorithm for finding the continued fraction for square roots, you should be able to find resources online with a search, but can start by taking a look at this question.

Answer 3

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) #print first 20 solutions when N=92

""" the smallest solution is 1151,120 where 1151 ^2-1= 92 * 120 ^2 (from wikipedia). (I'm not sure if it's the same as wikipedia recursion, but in this case the following recursion applies:

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)

"""