testing header
Math Goodies is a free math help portal for students, teachers, and parents.
|
 Free MathNewsletter
Interactive Math Goodies Software

Math Forums @ Math Goodies
Home | Profile | Register | Active Topics | Members | Search | FAQ
 Username: Password: Save Password Forgot your Password?
 All Forums  Homework Help Forums  Algebra  Pell type equations New Topic  Reply to Topic  Printer Friendly
Author  Topic

mathFan
New Member

Ireland
1 Posts

 Posted - 04/26/2012 :  05:49:10 Hi,I've been reading the following pagehttp://www-history.mcs.st-andrews.ac.uk/HistTopics/Pell.htmlabout obtaining solutions to Pell type equations.I am struggling on how to use the information to work with5x+20=yIt is obvious that one solution is x=1, y=5The next solution is (4, 10) but I require x and y to be coprimeThrough 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
59 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 areCV....4/1......5/1......19/4......24/5......211/44......235/49.....916/91......1151/240N........-7.......+2........-7.........+1...........-7............+2...........-7................+1Clearly 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/169N.........-1........+1......-1.........+1...........-1...........+1............-1By 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/1292N.........-1.......+1.........-1.............+1............-1................+1For \/10 where a = 3, the continued fraction leads to:CV......3/1......19/6......117/37......721/228......4443/1405......27379/8658N.........-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 withx/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 fromn......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......10C = 15y^2 + 1....6.....21....46....81....126...181...246...321...406...501C = 25y^2 + 2....7.....22....47....82....127...182...247...322...407...502C = 35y^2 + 3....8.....23....48....83....128...183...248...323...408...503C = 45y^2 + 4....9.....24...49....84....129...184...249...324...409...504C = 55y^2 + 5...10....25....50....85....130...185...250...325...410...505C = 65y^2 + 6...11....26....51....86....131...186...251...326...411...506C = 75y^2 + 7...12....27....52....87....132...187...252...327...412...507C = 85y^2 + 8...13....28....53....88....133...188...253...328...413...508C = 95y^2 + 9...14....29....54....89....134...189...254...327...414...509C = 105y^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 ofx^2 - 2y^2 = 2 where D + C = 4x^2 - 3y^2 = 1x^2 - 4y^2 = 0x^2 - 5y^2 = -1x^2 - 6y^2 = -2x^2 - 7y^2 = -3x^2 - 8y^2 = -4.x/y = 3/1 is the solution for the family ofx^2 - 5y^2 = 4 where D + C = 9x^2 - 6y^2 = 3x^2 - 7y^2 = 2x^2 - 8y^2 = 1x^2 - 9y^2 = 0x^2 - 10y^2 = -1x^2 - 11y^3 = -2x^2 - 12y^2 = -3x^2 - 13y^2 = -4x^2 - 14y^2 = -5x^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 = 16x/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 = 25x/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^2Assume \/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 = 1r..........1......2......3......4......5......6D.........2......3......4......5......6......7r^2.......1......4......9.....16....25.....36x/y.....3/2...4/2...5/2....6/2...7/2....8/2 x = r + 2 and y = 2a.a = 2r..........1......2......3.......4......5......6D.........5......6......7.......8......9.....10r^2.......1......4......9......16....25.....36x/y.....9/4..10/4..11/4..12/4..13/4..14/4 x = r + 8 and y = 2a.a = 3r..........1......2.......3......4......5.......6D........10....11.....12....13.....14.....15r^2.......1......4.......9.....16.....25.....36x/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........6r^2 = 1D......2......5......10......17......26.......37......= n^2 + 1x/y..3/2...9/4....19/6...33/8...51/10..73/12 r^2 = 4D......3......6......11......18......27.......38......= n^2 + 2x/y..4/2...10/4..20/6...34/8...52/10...74/12r^2 = 9D......4......7......12......19.......28.......39......= n^2 + 3x/y..5/2...11/4...21/6...35/8...53/10...75/12r^2 = 16D......5......8......13.......20.......29........40......= n^2 + 4x/y..6/2...12/4..22/6....36/8....54/10....76/12Values 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......63x/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........65x/y..............3/2...9/4...19/6..33/8..51/10..73/12..99/14..129/16 x = 2t^2 + 1 and y = 2tD = t^2 - 2....-1......2......7.....14......23......34.......47......62x/y..............0/1...3/2...8/3...15/4...24/5...35/6....48/7....63/8 x = t^2 - 1 and y = tD = t^2 - t......0......2......6......12......20......30......42......56x/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......48x/y..2/1...3/1.....4/1.....5/1.....6/1.....7/1For y = 2D = n(n + 1), x = 2n + 1D......2......6......12......20......30......42......56x/y..3/2...5/2.....7/2.....9/2....11/2...13/2...15/2For y = 3D = 9n^2 - 2n and x = 9n - 1 or D = 9n^2 + 2n and x = 9n + 1D......7......11......32......40......75......87......136......152x/y..8/3...10/3...17/3....19/3...26/3...28/3.....35/3.....37/3For y = 4D =4n^2 + n, x = 8n + 1 or D = 4n^2 + 7n + 3 and x = 8n + 7.D......5......14......18......33......39......60......68......95x.....9/4...18/4....17/4...23/4...25/4...31/4....33/4...39/4For y = 5D = 25n^2 - 2n, x = 25n - 1 or D = 25n^2 + 2n and x = 25n + 1D......23......27......96......104......219......231......392x/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..........5x/y..2/1...7/4...25/15..97/56..362/209Solutions to x^2 - 3y^2 = -3 follow asn......1......2.......3.........4..........5x/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............5x/y..6/4..24/14..90/52..336/194..1254/724This 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)^nn......1........2............3............etc.x/y..9/4..161/72..2889/1292.....etc.Solutions to x^2 - 5y^2 = -5 follow asn.......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
 New Topic  Reply to Topic  Printer Friendly Jump To: Select Forum New Visitor Forum       Testing Forum Homework Help Forums       Basic Math and Pre-Algebra       Algebra       Geometry and Trigonometry       Pre-Calculus and Calculus       Probability and Statistics       Standardized Test Preparation Help       Miscellaneous Math Topics Educator Forum       Teacher Talk Parent Forum       Parent's Place  -------------------- Home Active Topics Frequently Asked Questions Member Information Search Page
 Math Forums @ Math Goodies © 2000-2004 Snitz Communications
 This page was generated in 0.18 seconds. Snitz Forums 2000
testing footer
About Us | Contact Us | Advertise with Us | Facebook | Blog | Recommend This Page

Copyright © 1998-2013 Mrs. Glosser's Math Goodies. All Rights Reserved.

A Hotchalk/Glam Partner Site - Last Modified 17 Jun 2013