Author |
Topic: x^2 - 61y^2 = 1 (Read 9084 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
x^2 - 61y^2 = 1
« on: Apr 2nd, 2004, 2:13am » |
 Quote  Modify
|
Find the least positive solution of the quadratic Diophantine equation x2 - 61y2 = 1.
|
|
 IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: x^2 - 61y^2 = 1
« Reply #1 on: Apr 2nd, 2004, 10:02am » |
Quote Modify
|
Pell Equation for 61.. wow the answer should be really huge.. 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: x^2 - 61y^2 = 1
« Reply #2 on: Apr 2nd, 2004, 4:12pm » |
Quote Modify
|
Playing with a calculator I stumbled on 17663190492–61*2261539802=1.
Actually, I'd really like to know how to solve these analytically. I believe that Pell's equations: x2–Dy2=[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: 1766319049/226153980, but I don't have a clue why? 
|
| « Last Edit: Apr 2nd, 2004, 4:23pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: x^2 - 61y^2 = 1
« Reply #3 on: Apr 3rd, 2004, 6:32am » |
Quote Modify
|
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 x2–61y2=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]61y2).
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 x2–61y2=1. However, it doesn't prove that it a sufficient condition and a solution will exist.
I don't understand! 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: x^2 - 61y^2 = 1
« Reply #4 on: Apr 3rd, 2004, 5:09pm » |
Quote Modify
|
(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?
|
| « Last Edit: Apr 3rd, 2004, 5:09pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: x^2 - 61y^2 = 1
« Reply #5 on: Apr 4th, 2004, 6:01am » |
Quote Modify
|
on Apr 3rd, 2004, 5:09pm, 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: [ a0(a1… ar) ], where a0 = [ [sqrt]d ], ar = 2a0, and a1, …, ar-1 is a palindromic sequence.
3. The solution of the Pell’s equation x2 - dy2 = 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 pr-1/qr-1 is the (r-1)-th convergent of [sqrt]d, then x, y are to be found from the equation x + y[sqrt]d = (pr-1 + qr-1[sqrt]d)2 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: p10/q10 = 29718/3805, so x = p102 + 61q102; y = 2 p10q10.
on Apr 3rd, 2004, 5:09pm, 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 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… 
|
| « Last Edit: Apr 4th, 2004, 10:35am by Barukh » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
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=a0+1/(a1+1/(a2+...))
x0=[sqrt]D, and ak=[xk], where [ ] represents the integer part function.
then xk+1=1/(xk+[xk])
My clever discovery, which you already outlined, Barukh, is the fact that after a0, we find that the sequence, a1, a2, ... ,ar-1, is palindromic. In addition you know that you've found ar (the last term of the periodic sequence, a1, ... , ar), because ar=2a0.
2nd Iterative Method (based on algebraic method for computing CFs):
At a particular stage, ak+f([sqrt]D)=ak+1/(1/fk([sqrt]D)), where fk([sqrt]D)=([sqrt]D–u)/v.
By rationalising 1/fk([sqrt]D), we get ak+1/(ak+1+fk+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 pk=ak*pk-1+pk-2 and qk=ak*qk-1+qk-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 Apr 4th, 2004, 6:01am, Barukh wrote:| The following sequence from On-Line Encyclopedia 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 x2–9739y2=1:
2004678915287129865051784235972681465598817784993286 048703987347587076305931512617412027372229926151890^2 - 9739*20313634766038988908316803031882483814532877863 673358783668788287930891909883492238723036864710413171^2 = 1
|
| « Last Edit: Apr 5th, 2004, 11:09am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: x^2 - 61y^2 = 1
« Reply #7 on: Apr 4th, 2004, 11:42pm » |
Quote Modify
|
Awesome, Sir Col! A master quality analysis! 
For everybody interested, I recommend the following extremely interesting article 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! 
|
| « Last Edit: Apr 4th, 2004, 11:43pm by Barukh » |
IP Logged |
|
|
|
bitRAKE
Newbie
Gender:
Posts: 1
|
 |
Re: x^2 - 61y^2 = 1
« Reply #8 on: Jan 5th, 2005, 10:56pm » |
Quote Modify
|
D=998799649 (92357 period length) 
How many digits in x for minimum solution?
[edit] Kind of silly not to post an odd period D. 
|
| « Last Edit: Jan 5th, 2005, 11:36pm by bitRAKE » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
square_root_continued_fractions.xls