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

Buy Math Goodies Software
testing left nav
Math Forums @ Math Goodies
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 Previous Topic Topic Next Topic  

mathFan
New Member

Ireland
1 Posts

Posted - 04/26/2012 :  05:49:10  Show Profile  Reply with Quote
Hi,

I've been reading the following page

http://www-history.mcs.st-andrews.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
Go to Top of Page

TchrWill
Advanced Member

USA
79 Posts

Posted - 02/12/2013 :  15:40:51  Show Profile  Reply with Quote
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.














Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
Math Forums @ Math Goodies © 2000-2004 Snitz Communications Go To Top Of Page
This page was generated in 0.12 seconds. Snitz Forums 2000
testing footer
About Us | Contact Us | Advertise with Us | Facebook | Blog | Recommend This Page




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

A Hotchalk/Glam Partner Site - Last Modified 22 Apr 2014