wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Pell of the form a*x^2 - b*y^2
        
(Message started by: Christine on Mar 15^th, 2016, 2:35pm)

Title: Pell of the form a*x^2 - b*y^2
Post by Christine on Mar 15^th, 2016, 2:35pm

Could you pleases show how to solve Pell equations of the type:

a*x^2 - b*y^2 = +/- 1

for example,

27*x^2 - 343*y^2 = -1

Title: Re: Pell of the form a*x^2 - b*y^2
Post by pex on Mar 16^th, 2016, 3:03am

As far as I know, you want x/y to be a convergent of the continued fraction of sqrt(b/a), because the only hope of getting ax² - by² close to zero is to try and make (x/y)² close to b/a. I don't know if there's anything more fancy that can be done than "keep trying until it works"; for your example, I find the following, letting x/y be successive convergents to sqrt(343/27):

Code:

......x .....y .rhs (annoying dots added to keep columns aligned)

......3 .....1 -100
......4 .....1 ..89
......7 .....2 .-49
.....25 .....7 ..68
.....57 ....16 .-85
.....82 ....23 .101
....139 ....39 .-36
....638 ...179 .125
....777 ...218 .-49
...2969 ...833 ..20
..27498 ..7715 .-67
..57965 .16263 .108
..85463 .23978 .-49
.314354 .88197 ..45
1342879 376766 ..-1

so x=1342879, y=376766 is a solution.

Title: Re: Pell of the form a*x^2 - b*y^2
Post by Grimbal on Mar 18^th, 2016, 7:33am

For approximating fractions, there is the Stern-Brocot tree, which is probably the same in different terms.