Author 
Topic 

mathFan
New Member
Ireland
1 Posts 
Posted  04/26/2012 : 05:49:10

Hi,
I've been reading the following page
http://wwwhistory.mcs.standrews.ac.uk/HistTopics/Pell.html
about obtaining solutions to Pell type equations.
I am struggling on how to use the information to work with
5x+20=y
It is obvious that one solution is x=1, y=5
The next solution is (4, 10) but I require x and y to be coprime
Through brute force I know the next few solutions are (11, 25), (29, 65) and (199, 445).
I just can't seem to use the information on the above page to obtain these solutions.
A kick start would be greatly appreciated.
Many thanks 
Edited by  mathFan on 04/26/2012 08:19:55 


TchrWill
Advanced Member
USA
79 Posts 
Posted  02/12/2013 : 15:40:51

Might the following be of some use to you?
Noteworthy facts regarding the solution of Pell equations.
\/D = square root of D or \/ = square root symbol
* Solutions to x^2  Dy^2 = +/1 are found among the convergants of \/D. The sequence of convergants derived from the continued fraction of \/D lead to varying solutions to x^2  Dy^2 = +/C within which lie the solution(s) to x^2  Dy^2 = +/1. The sequence of solutions is ultimately periodic, repeating itself infinitely. If a solution to x^2  Dy^2 = +/1 does not show up within the first repeating period of solutions, then there is no solution.
Consider x^2  23y^2 = +/N.
Continued fraction of \/23: sqrt(23) = 4 + 1 ...................________ ....................1.. +.. 1 ........................________ .........................3 + 1 ............................_________ .............................1 + 1 ............................... .________ ..................................8 + 1 ......................................_______ .......................................etc.
The convergants derived from this continued fraction and the resulting N's are CV....4/1......5/1......19/4......24/5......211/44......235/49.....916/91......1151/240 N........7.......+2........7.........+1...........7............+2...........7................+1
Clearly the solutions repeat every 4 convergants. There being no N = 1 within the repeating pattern, there is no solution for x^2  23y^2 = 1.
* Every convergant pn/qn of the continued fraction of \/D provides a solution x = pn and y = qn of x^2 + Dy^2 = +/N. where N < (1 + 2\/D).
* Over the centuries, mumerous methods have been defined for estimating the first, or minimum, convergant square root of D ......The most popular was defined by Aryabhatta as sqrtD = sqrt(a^2 + r) = a + r/2a where "a^2" being the nearest square below D. ......El Hassar refined this to sqrtD = sqrt(a^2 + r) = a + r/2a  [(r/2a)^2]/[2(a + r/2a)], "a^2" being the nearest square below D. ......Heron and Archimedes added a twist by stating it as sqrtD = sqrt(a^2 + r) = a+/r/2a), "a" being the nearest square to D. ......Alkarkhi added another twist in sqrtD = sqrt(a^2 + r) = a + r/(2a+1). ......Alkalcadi added yet another twist in sqrtD = sqrt(a^2 + r) = (r + 1)/(2a + r), r > a. ......Newton's noteworthy contribution was sqrtD = sqrt(a^2 + r) = (a + D/a)/2.
* If x = pn and y = qn is the minimal solution to x^2  Dy^2 = 1, then subsequent solutions derive from (x + y\/D)^(2n + 1), n = 1, 2, 3, ...etc.
* All irrational numbers of the form (a^2 + 1) can be converted to continued fraction convergants in the same way that \/2 can be. \/D = sqrt(a^2 + 1), "a" equaling the nearest integer square root, making the first convergant n/d = a/1 = 1/1. sqrt(a^2 + 1) = 1.+.....1 ..........................________ ...........................2a.+....1 ...............................________ ................................2a.+....1 ....................................________ .....................................2a.+....1 .........................................________ ..........................................2a.+....1 ..............................................________ ................................................2a.+.etc.
For \/2 where a = 1: CV......1/1......3/2......7/5......17/12......41/29......99/70......239/169 N.........1........+1......1.........+1...........1...........+1............1
By inspection, the denominator of the next convergant derives from summing the numerator and denominator of the previous convergant or d = 1 + 1 = 2. The numerator of the next convergant derives from summing the new denominator to the previous denominator or 2 + 1 = 3. Thus, the second convergant is 3/2. In the same way, the third convergant becomes 5/3 from 2 + 3 = 5 and 5 + 2 = 7. This holds for \/2 but not for subsequent \/D = \/(a^2 + 1).
For \/5 where a = 2, the continued fraction leads to: CV......2/1......9/4......38/17......161/72......682/305......2889/1292 N.........1.......+1.........1.............+1............1................+1
For \/10 where a = 3, the continued fraction leads to: CV......3/1......19/6......117/37......721/228......4443/1405......27379/8658 N.........1.........+1..........1.............+1................1....................+1
* Close approximations of \/D can be obtained by successively adding the numerators and denominators of the closest estimates of \/D on either side of the actual \/D. To clarify this, an example will illustrate the process. For \/10, the closest integer less than the \/10 is 4 while the closest integer more than \/10 is 5 making the first x/y estimates 4/1 and 5/1 on either side of the actual \/D. Adding the two numerators and two denominators leads to a new estimate of 9/2 which is more than the actual \/10. Labeling the 4/1 estimate as "", the 5/1 estimate as "+", and the 9/2 estimate as "+", we add the latest estimate to the nearest estimate of opposite sign or 9 + 4 = 13 and 2 + 1 = 3 making the next estimate 13/3 which is also larger than the actual \/10 thereby getting the label of "+". Adding this latest "+" estimate to the nearest "" estimate, we get 13 + 4 and 3 + 1 to arrive at the next estimate of 17/4, also a "+". Continuing in this manner, we end up with
x/y......4/1......5/1......9/2......13/3......17/4......21/5......25/6......29/7......33/8......37/9......70/17......103/25......etc. Sign...............+........+..........+...........+..........+..........+..........+..........+...............................................etc. N.........1.......+8......+13......+16.......+17......+16.......+13.......+8.........+1.........8..........13..........16.........etc. The first estimate to satisfy x^2  17y^2 = +1 is therefore 33/8 which could just as easily have been obtained from Newton's method of \/10 = \/(4^2 + 1) = 4 + 1/8 = 33/8.
* If x = p and y = q is a minimum solution to x^2  Dy^2 = +1 (exclusive of 1/0), subsequent solutions derive from n......1......2...........3...................4........................5..................etc. x......1......p......(2p^2  1)......(4p^3  3p)......(8p^4  8p^2 + 1)......etc. y......0......q.........2pq...........(4qp^2  q)..........(4qp^4  4pq)........etc. If A and B are two consecutive values of either "x" or "y", the next value derives from 2pB  A. Example: x^2  2y^2 = +1. From Newton's estimation method, the minimum p/q solution to \/2 is \/(1^2 + 1) = 1 + 1/2 = 3/2 = p/q. Then, x3 = 2(3)^2  1 = 17 and y3 = 2(3)2 = 12. .........x4 = 4(3)^3  3(3) = 99 and y4 = 4(2)3^2  2 = 70. .........x5 = 8(3)^4  8(3)^2 + 1 = 577 and y5 = 2(3)70  12 = 408. Therefore, n......1......2......3......4......5......etc. ...............x......1......3.....17....99....577 ...............y......0......2.....12....70....408....etc.
* Given x^2  Dy^2 = k1 and x^2  Dy^2 = k2. If p and q is a solution to x^2  Dy^2 = k1 and r and s is a solution to x^2  Dy^2 = k2, then x = pr+/Dqs and y = ps+/qr is a solution to x^2  Dy^2 = (k1k2). Example: 18/8 is a solution to x^2  5y^2 = 4 and 5/2 is a solution to x^2  5y^2 = 5. Therefore, x = 18(5) + 5(8)2 = 170 and y = 18(2) +8(5) = 76 is a solution to x^2  5y^2 = 20 as is ...............x = 18(5)  5(8)2 = 10 and y = 18(2)  8(5) = 4 = 4.
More generally, if x = p and y = q is a solution to x^2  Dy^2 = k, then x = p^2 + Dq^2 and y = 2pq is a solution to x^2  Dy^2 = k^2.
It would appear that one could work backwards from x^2  5y^2 = 20 to determine solutions to x^2  5y^2 = 10 and x^2  5y^2 = 10. Since all perfect squares must end in a 0, 1, 4, 5, 6 or 9, 5y^2 + 2 cannot result in a square indicating that there is no solution to x^2  5y^2 = 2.
By means of the same logic, it is possible to identify that there are no solutions to many values of C in x^2  5y^2 = C. While numerous values of C will result in 5y^2 + C ending in 0, 1, 4, 5, 6 or 9, they are not necessarily squares. Highlighted values indicate there is a solution. y...............1......2......3......4......5.......6......7......8......9......10 C = 1 5y^2 + 1....6.....21....46....81....126...181...246...321...406...501 C = 2 5y^2 + 2....7.....22....47....82....127...182...247...322...407...502 C = 3 5y^2 + 3....8.....23....48....83....128...183...248...323...408...503 C = 4 5y^2 + 4....9.....24...49....84....129...184...249...324...409...504 C = 5 5y^2 + 5...10....25....50....85....130...185...250...325...410...505 C = 6 5y^2 + 6...11....26....51....86....131...186...251...326...411...506 C = 7 5y^2 + 7...12....27....52....87....132...187...252...327...412...507 C = 8 5y^2 + 8...13....28....53....88....133...188...253...328...413...508 C = 9 5y^2 + 9...14....29....54....89....134...189...254...327...414...509 C = 10 5y^2 + 10.15....30....55....90....135...190...255...328...415...510
* Given x^2  Dy^2 = C When D = a^2, then a^2y^2 + C = x^2. Diophantus equates x^2 = (ay+/m)^2 = a^2y^2 + C. Then, y = +/(C  m^2)/2ma, m = 1, 2, 3, 4...etc. ("x" and the assumed sign to give "x" a positive value) This leads to rational solutions only.
When C = c^2, he lets x = my+/c or Dy^2 + c^2 = (my+/c)^2 from which y = +/(2mc/(D  m^2). . Example: For x^2  5y^2 = 9, c = 3, D = 5, m = 2, y = 2(2)3/(5  4) = 12 and x = 27.
* When D = a^2 and C + D is a square, x = sqrt(C + D) and y = 1. Examples: x^2  4y^2 = 9 yields x = sqrt(4 + 5) = 3 and y = 1. x^2  4y^2 = 12 yields x = sqrt(4 + 12) = 4 and y = 1. x^2  4y^2 = 21 yields x = sqrt(4 + 21) = 5 and y = 1. x^2  9y^2 = 7 yields x = 4 and y = 1. x^2  9y^2 = 16 yields x = 5 and y = 1. x^2  9y^2 = 27 yields x = 6 and y = 1.
* When D + C = a square, x = sqrt(D + C) and y = 1 for a family of Pell equations satisfying D + C = a square. Example: x/y = 2/1 is the solution for the family of x^2  2y^2 = 2 where D + C = 4 x^2  3y^2 = 1 x^2  4y^2 = 0 x^2  5y^2 = 1 x^2  6y^2 = 2 x^2  7y^2 = 3 x^2  8y^2 = 4.
x/y = 3/1 is the solution for the family of x^2  5y^2 = 4 where D + C = 9 x^2  6y^2 = 3 x^2  7y^2 = 2 x^2  8y^2 = 1 x^2  9y^2 = 0 x^2  10y^2 = 1 x^2  11y^3 = 2 x^2  12y^2 = 3 x^2  13y^2 = 4 x^2  14y^2 = 5 x^2  15y^2 = 6.
x/y = 4/1 is the solution to the family ranging from x^2  10y^2 = 6 to x^2  24y^2 = 8 where D + C = 16 x/y = 5/1 is the solution to the family ranging from x^2  17y^2 = 8 to x^2  35y^2 = 10.where D + C = 25 x/y = sqrt(D + C)/1 from x^2  [{sqrt(D + C)  1}^2 + 1]y^2 = C to x^2  [{sqrt(D + C) + 1}^2  1]y^2 = C.
* Diophantus stated that x^2  Dy^2 = c^2 has no solutions unless D is the sum of two squares. Example: From x^2  5y^2 = 9, x = 6 and y = 3.
* Given the Pell equation of the form x^2  Dy^2 = c^2 Assume \/D = \/(a^2 + r). The minimal solution is therefore x/y = a + r/2a = (2a^2 + r)/2a making x = 2a^2 + r and y = 2a. x = 2a^2 + r and y = 2a is the solution to x^2  Dy^2 = c^2 = r^2. Example: x^2  7y^2 = c^2. ...............\/7 = a + r/2a = 2 + 3/4 = 11/4 or x = 2(2)^2 + 3 = 11 and y = 2(2) = 4 (r = 3). ...............Therefore, 11/4 is the minimum solution to x^2  7y^2 = r^2 = 9. In general, given x^2  Dy^2 = c^2 (r^2). With D = a^2 + r, x = 2a^2 + r and y = 2a is the minimum solution to x^2  Dy^2 = r^2.
Sample data: a = 1 r..........1......2......3......4......5......6 D.........2......3......4......5......6......7 r^2.......1......4......9.....16....25.....36 x/y.....3/2...4/2...5/2....6/2...7/2....8/2 x = r + 2 and y = 2a. a = 2 r..........1......2......3.......4......5......6 D.........5......6......7.......8......9.....10 r^2.......1......4......9......16....25.....36 x/y.....9/4..10/4..11/4..12/4..13/4..14/4 x = r + 8 and y = 2a. a = 3 r..........1......2.......3......4......5.......6 D........10....11.....12....13.....14.....15 r^2.......1......4.......9.....16.....25.....36 x/y....19/6..20/6..21/6..22/6..23/6..24/6 x = r + 18 and y = 2a.
Tabulated another way. n.......1......2......3........4........5........6 r^2 = 1 D......2......5......10......17......26.......37......= n^2 + 1 x/y..3/2...9/4....19/6...33/8...51/10..73/12 r^2 = 4 D......3......6......11......18......27.......38......= n^2 + 2 x/y..4/2...10/4..20/6...34/8...52/10...74/12 r^2 = 9 D......4......7......12......19.......28.......39......= n^2 + 3 x/y..5/2...11/4...21/6...35/8...53/10...75/12 r^2 = 16 D......5......8......13.......20.......29........40......= n^2 + 4 x/y..6/2...12/4..22/6....36/8....54/10....76/12
Values of D for which there are solutions to x^2  Dy^2 = c^2 derive from D = n^2 + c = n^2 + r. For these D's, x = 2D  c or 2D  r = 2n^2 + c = 2n^2 + r and y = 2n.
* MInimum solutions to x^2  Dy^2 = +1 are easily derivable when D is of the form t^2 1, t^2 + 1, t^2  2, t^2 + 2, t^2  t and t^2 + t. t...................1......2......3......4.......5.......6........7.......8......etc. D = t^2  1.....0......3......8.....15.....24.....35.......48......63 x/y..............1/1...2/1...3/1....4/1....5/1....6/1......7/1.....8/2 x = t and y = 1.
D = t^2 + 1....2......5.....10.....17.....26.......37......50........65 x/y..............3/2...9/4...19/6..33/8..51/10..73/12..99/14..129/16 x = 2t^2 + 1 and y = 2t
D = t^2  2....1......2......7.....14......23......34.......47......62 x/y..............0/1...3/2...8/3...15/4...24/5...35/6....48/7....63/8 x = t^2  1 and y = t
D = t^2  t......0......2......6......12......20......30......42......56 x/y..............1/1....3/2...5/2....7/2....9/2.....11/2....13/2..15/2 x = 2n  1 and y = 2.
* For an assumed value of "y", expressions are derivable for compatible values of "D" and "x" satisfying x^2  Dy^2 = +1. Examples: For y = 1. D = n(n + 2), x = sqrt(D + 1) D......3......8......15......24......35......48 x/y..2/1...3/1.....4/1.....5/1.....6/1.....7/1
For y = 2 D = n(n + 1), x = 2n + 1 D......2......6......12......20......30......42......56 x/y..3/2...5/2.....7/2.....9/2....11/2...13/2...15/2
For y = 3 D = 9n^2  2n and x = 9n  1 or D = 9n^2 + 2n and x = 9n + 1 D......7......11......32......40......75......87......136......152 x/y..8/3...10/3...17/3....19/3...26/3...28/3.....35/3.....37/3
For y = 4 D =4n^2 + n, x = 8n + 1 or D = 4n^2 + 7n + 3 and x = 8n + 7. D......5......14......18......33......39......60......68......95 x.....9/4...18/4....17/4...23/4...25/4...31/4....33/4...39/4
For y = 5 D = 25n^2  2n, x = 25n  1 or D = 25n^2 + 2n and x = 25n + 1 D......23......27......96......104......219......231......392 x/y..24/5...26/5....49/5....51/5.....74/5.....76/5.....99/5
* If a Pell equation has the characteristic of C/D = a square, solutions are derivable in a unique three step process outlined below.
Given x^2  Dy^2 = C where C/D = a perfect square. Define solutions to x^2  Dy^2 = +1 from any of the methods descried earlier. Then, for x^2  Dy^2 = D, the "y" values are the same as the "x" values from x^2  Dy^2 = +1 and the "x" values follow directly. Then, the "x" and "y" solutions to x^2  Dy^2 = C are sqrt(C/D) times the "x" anf "y" solutions to x^2  Dy^2 = D.
Example: Given x^2  3y^2 = 12. The minimum solution to x^2  3y^2 = +1 derives from sqrtD = x/y = sqrt(a^2 + r) = a + r/2a = 1 + 2/2 = 2/1. Subsequent solutions follow from (2 + 1\/3)^n. n......1......2.......3.........4..........5 x/y..2/1...7/4...25/15..97/56..362/209
Solutions to x^2  3y^2 = 3 follow as n......1......2.......3.........4..........5 x/y..3/2..12/7..45/26..168/97..627/362 the "y" values being identical to the "x" values from x^2  3y^2 = +1.
Solutions to x^2  3y^2 = 12 then become sqrt(C/D) = sqrt(4) = 2 times the solutions to x^2  3y^2 = 3. n......1.......2........3..........4............5 x/y..6/4..24/14..90/52..336/194..1254/724
This example problem happens to be the means for determining all Heronian triangles with consecutive sides. Each "y" value in the infinite number of solutions to x^2  3y^2 = 12 is the middle side of a consecutive sided Heronian triangle.
Example: Given x^2  5y^2 = 45. The minimum solution to x^2  5y^2 = +1 derives from sqrtD = x/y = 2 + 1/4 = 9/4. Subsequent solutions follow from (9 + 4\/5)^n n......1........2............3............etc. x/y..9/4..161/72..2889/1292.....etc.
Solutions to x^2  5y^2 = 5 follow as n.......1.........2.............3..........etc. x/y..20/9..360/161..6460/2889...etc.
Solutions to x^2  5y^2 = 45 then become sqrt(45/5) = sqrt9 = 3 times the solutions to x^2  5y^2 = 5. n......1.............2...............3............etc. x/y..60/27..1080/483..19380/8667....etc.




Topic 


