wu :: forums - Print Page


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

        riddles >> medium >> x^2 - 61y^2 = 1
        
(Message started by: Barukh on Apr 2^nd, 2004, 2:13am)

Title: x^2 - 61y^2 = 1
Post by Barukh on Apr 2^nd, 2004, 2:13am

Find the least positive solution of the quadratic Diophantine equation x² - 61y² = 1.

Title: Re: x^2 - 61y^2 = 1
Post by Sameer on Apr 2^nd, 2004, 10:02am

Pell Equation for 61.. wow the answer should be really huge.. ::)

Title: Re: x^2 - 61y^2 = 1
Post by Sir Col on Apr 2^nd, 2004, 4:12pm

Playing with a calculator I stumbled on [hide]1766319049²–61*226153980²=1[/hide]. ::)

Actually, I'd really like to know how to solve these analytically. I believe that Pell's equations: x²–Dy²=[pm]1 have something to do with the convergent expansion of the continued fraction of [sqrt]D.

So in this example, [sqrt]61=[7,(1,4,3,1,2,2,1,3,4,1,14)].

However, working sequentially through the approximations, none of them give a solution (each being x/y):
7/1, 8/1, 39/5, 125/16, 164/21, 453/58, 1070/137, 1523/195, 5639/722, 24079/3083, 29718/3805, 440131/56353.

[e]Added...[/e]
Okay, I'm sad. I worked through and found that the 22nd iteration is the desired fraction: [hide]1766319049/226153980[/hide], but I don't have a clue why? ???

Title: Re: x^2 - 61y^2 = 1
Post by Sir Col on Apr 3^rd, 2004, 6:32am

It's me again...

I've been playing with the equation, and I can see why there is a loose connection between the roots of the equation and a rational approximation of [sqrt]61.

From x²–61y²=1, we get, (x–[sqrt]61y)(x+[sqrt]61y)=1, so, x–[sqrt]61y=1/(x+[sqrt]61y).

Dividing by y give, x/y–[sqrt]61=1/(xy+[sqrt]61y²).

For very large x and y, RHS will be very small, and this can only happen if x/y is very close to [sqrt]61. In other words, the truth of this equation (x/y being a close approximation of [sqrt]61) is a necessary condition for x²–61y²=1. However, it doesn't prove that it a sufficient condition and a solution will exist.

I don't understand! :'(

Title: Re: x^2 - 61y^2 = 1
Post by Sir Col on Apr 3^rd, 2004, 5:09pm

(It seems that I'm talking to myself here) ;)

Wow! I've found a really quick way of generating the terms of the continued fraction and an iterative method for producing the rational approximations to the square root.

It seems that in most cases the solution can be found after the pth iteration, where p is the period of the continued fraction. However, in some cases the solution occurred at iteration, 2p. Here are the cases for D<100:

13: 3,(1,1,1,1,6) [period=5]
649^2-13*180^2=1 [iteration=10]

29: 5,(2,1,1,2,10) [period=5]
9801^2-29*1820^2=1 [iteration=10]

41: 6,(2,2,12) [period=3]
2049^2-41*320^2=1 [iteration=6]

53: 7,(3,1,1,3,14) [period=5]
66249^2-53*9100^2=1 [iteration=10]

58: 7,(1,1,1,1,1,1,14) [period=7]
19603^2-58*2574^2=1 [iteration=14]

61: 7,(1,4,3,1,2,2,1,3,4,1,14) [period=11]
1766319049^2-61*226153980^2=1 [iteration=22]

73: 8,(1,1,5,5,1,1,16) [period=7]
2281249^2-73*267000^2=1 [iteration=14]

74: 8,(1,1,1,1,16) [period=5]
3699^2-74*430^2=1 [iteration=10]

85: 9,(4,1,1,4,18) [period=5]
285769^2-85*30996^2=1 [iteration=10]

89: 9,(2,3,3,2,18) [period=5]
500001^2-89*53000^2=1 [iteration=10]

97: 9,(1,5,1,1,1,1,1,1,5,1,18) [period=11]
62809633^2-97*6377352^2=1 [iteration=22]

What I've not been able to establish is why I can't find a solution for D=151. Any ideas?

Title: Re: x^2 - 61y^2 = 1
Post by Barukh on Apr 4^th, 2004, 6:01am

on 04/03/04 at 17:09:23, Sir Col wrote:

(It seems that I'm talking to myself here) ;)

Sir Col, you certainly are not talking to yourself ;)! I followed your posts carefully and was impressed by your findings.

I learned about Pell’s equations just a few days ago. You are right, they are intimately related to square root approximations with convergents of continued fractions. In what follows, I’ll present briefly what I know about this problem (sure, all this and much more may be easily found on the web, but it’s good to have it concentrated at one place). Proofs are omitted; they are commonly lengthy albeit elementary.

Let d be a positive integer which is not a perfect square.

1. The continued fraction (CF) of [sqrt]d is periodic. [An even more general statement says that CF of irrational number is periodic iff that number is a root of a quadratic equation]

2. CF of [sqrt]d has the following structure: [ a₀(a₁… a_r) ], where a₀ = [ [sqrt]d ], a_r = 2a₀, and a₁, …, a_r-1 is a palindromic sequence.

3. The solution of the Pell’s equation x² - dy² = 1 in positive integers exists for every d that is not a perfect square. In fact, an infinite number of solutions exist.

4.If r is even, then all the solutions are given by the n(r-1) convergents of [sqrt]d for n = 1, 2, … If r is odd, than all the solutions are given by the 2n(r-1) convergents of [sqrt]d for n = 1, 2, …

5. In case r is odd, finding the least solution in positive integers may be simplified as follows: If p_r-1/q_r-1 is the (r-1)-th convergent of [sqrt]d, then x, y are to be found from the equation x + y[sqrt]d = (p_r-1 + q_r-1[sqrt]d)² by expanding the rhs and equating rational and irrational parts.

The period of expansion r, as a function of d, does not have “smooth” behavior, but it does increase on a large scale.

For d=61, as Sir Col already computed, r=11, so the trick described in the last paragraph, will work: p₁₀/q₁₀ = 29718/3805, so x = p₁₀² + 61q₁₀²; y = 2 p₁₀q₁₀.

on 04/03/04 at 17:09:23, Sir Col wrote:

Wow! I've found a really quick way of generating the terms of the continued fraction and an iterative method for producing the rational approximations to the square root.

Good! Could you please present it here?

Quote:

What I've not been able to establish is why I can't find a solution for D=151. Any ideas?

For d = 151, r = 20 (try this with your method!) – an even number. So, you actually need only 20 iterations to get to the solution… The following sequence from On-Line Encyclopedia (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A013645) has even more impressive examples (try to find the period for d = 9739).

Modified the post to fix errors (due to bad understanding). Sorry for inconvenience… :(

Title: Re: x^2 - 61y^2 = 1
Post by Sir Col on Apr 4^th, 2004, 11:16am

Aha! That makes perfect sense with my recent discoveries. I finished school on Friday for the Easter break and I've had the fortune to find plenty of time this weekend to explore continued fractions and Pell's equation. Absolutely fascinating!

My first algorithm, which seemed to fail at D=151, was good, but it was unworkable on a computer; it required too much decimal precision for CFs containing longer periods.

However, I have since created a more reliable algorithm...

1st Iterative Method (based on the definition of CFs):
[sqrt]D=a₀+1/(a₁+1/(a₂+...))

x₀=[sqrt]D, and a_k=[x_k], where [ ] represents the integer part function.
then x_k+1=1/(x_k+[x_k])

My clever discovery, which you already outlined, Barukh, is the fact that after a₀, we find that the sequence, a₁, a₂, ... ,a_r-1, is palindromic. In addition you know that you've found a_r (the last term of the periodic sequence, a₁, ... , a_r), because a_r=2a₀.

2nd Iterative Method (based on algebraic method for computing CFs):

At a particular stage, a_k+f([sqrt]D)=a_k+1/(1/f_k([sqrt]D)), where f_k([sqrt]D)=([sqrt]D–u)/v.
By rationalising 1/f_k([sqrt]D), we get a_k+1/(a_k+1+f_k+1([sqrt]D))

The method for finding convergents is really slick...

Define p_-2=0, p_-1=1, q_-2=1, q_-1=0.

Then p_k=a_k*p_k-1+p_k-2 and q_k=a_k*q_k-1+q_k-2

If you're interested, I've attached an Excel spreadsheet of the CFs, period (r), rth convergent, solution to Pell equation, and number of convergent where solution is found for D=2,3,...,200.

[e]Added...[/e]

on 04/04/04 at 06:01:36, Barukh wrote:

The following sequence from On-Line Encyclopedia (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A013645) has even more impressive examples (try to find the period for d = 9739).

D=9739 has a fairly humble period of 210; in fact 9949 has a period of 217 and is the largest below 10000. I got my programme to run through CFs upto D=1000000, and the longest period was at D=969406, period length, 2664. With the above algorithm it only took a few minutes to search all the way up to one million!

For your information, here is the minimal solution to x²–9739y²=1:

2004678915287129865051784235972681465598817784993286 048703987347587076305931512617412027372229926151890^2 - 9739*20313634766038988908316803031882483814532877863 673358783668788287930891909883492238723036864710413171^2 = 1

Title: Re: x^2 - 61y^2 = 1
Post by Barukh on Apr 4^th, 2004, 11:42pm

Awesome, Sir Col! A master quality analysis! :D:D:D

For everybody interested, I recommend the following extremely interesting article (http://www.ams.org/notices/200202/fea-lenstra.pdf) by H. Lenstra – a Dutch mathematician who proposed an Elliptic Curve Method for integer factorization. In this paper, Lenstra treats historical and computational aspects of solving Pell’s equations. It turns out that Pell has nothing to do with these equations! ;D

Title: Re: x^2 - 61y^2 = 1
Post by bitRAKE on Jan 5^th, 2005, 10:56pm

D=998799649 (92357 period length) :o

How many digits in x for minimum solution?

[edit] Kind of silly not to post an odd period D. :P