| Author |
 Topic  |
|
|
mathFan
New Member
Ireland
1 Posts |
 Posted - 04/26/2012 : 05:49:10
|
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 |
 |
|
|
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 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 |
|
|
|
Interactive Math Goodies Software
Pell type equations
