008: Pell Equations
Note 1: For x2-dy2 = ±4 to have a solution in odd integers a necessary (but not sufficient) condition is that d is odd number of form 8n+5. (There are exceptions like d = 37, 101, etc. which have no odd solutions.)
Note 2: For odd d, if x2-dy2 = -4 is solvable, then so is x2-dy2 = -1. But for even d, this does not necessarily apply. For example, x2-20y2 = -4 has the soln {4,1}, but x2-20y2 = -1 has none.
4. A. Cunningham, R. Christie
By doing the transformations a) {x√2, y√2} = {p, q}, and b) {x√-2, y√-2} = {p, q}, on the Brouncker-Wallis theorem, we get the variants,
(p2-1)2 - d(pq)2 = 1, if p2-dq2 = 2
(p2+1)2 - d(pq)2 = 1, if p2-dq2 = -2
If d = 8n+r is prime, then the ff always have solns:
d = 8n+1 for u2-dv2 = -1;
d = 8n+3 for p2-dq2 = -2;
d = 8n+5 for u2-dv2 = -1;
d = 8n+7 for p2-dq2 = 2.
Theorem: “Primes of form d = 4n+1 solve x2-dy2 = -1, while those of form d = 4n-1 solve one case of x2-dy2 = ±2 (Legendre). For such d, the fundamental soln to x2-dy2 = ±2 leads to the one for u2-dv2 = 1.”
5. F. Arndt
(2pr2-1)2 - pq(2rs)2 = 1, if pr2-qs2 = 1
(pr2+qs2)2 - pq(2rs)2 = 1, if pr2-qs2 = ±1
(pr2-1)2 - pq(rs)2 = 1, if pr2-qs2 = 2
(pr2+1)2 - pq(rs)2 = 1, if pr2-qs2 = -2
which are generalizations of the identities discussed previously.
Q: Any other transformations?
1. W. Brouncker, J. Wallis
Brouncker-Wallis theorem: “If x2-dy2 = -1 (eq.1), then (2x2+1)2-d(2xy)2 = 1.”
Proof: Square both sides of eq.1,
(x2-dy2)2 = (-1)2
(x2+dy2)2 - d(2xy)2 = 1
Since dy2 = x2+1 from eq.1, then,
(2x2+1)2-d(2xy)2 = 1
Example:
x2-13y2 = -1; {x,y} = {18, 5),
p2-13q2 = 1; {p,q}= {2(182)+1, 2(18)(5)} = {649, 180}
This shows that fundamental solns to the negative Pell equation, when they exist, are smaller than those for the positive case. After a challenge by Frenicle de Bessy, Brouncker solved x2-313y2 = 1 by solving the relatively easier negative case. (Note: Letting {x,y} = {u√-1, v√-1} gives the purely positive variant: “If u2-dv2 = 1, then (2u2-1)2-d(2uv)2 = 1”, which implies one soln leads to some of the other solns.)
2. A. Cayley
Theorem: “If there is an odd fundamental soln {u,v} to u2-dv2 = ±4, then it leads to the fundamental soln for x2-dy2 = ±1.”
Case 1: If u2-dv2 = 4, and {x,y} = {(u2-3)u/2, (u2-1)v/2}, then x2-dy2 = 1.
Ex. Let d = 5. Then {u,v} = {3,1}, and {x,y} = {9, 4}.
Case 2: If u2-dv2 = -4, and {x,y} = {(u2+3)u/2, (u2+1)v/2}, then x2-dy2 = -1.
Ex. Let d = 5. Then {u,v} = {1,1} and {x,y} = {2, 1}.
In contrast, let d = 37. Since the fundamental soln of the negative case is even {u,v} = {12, 2}, using the formula does not lead to fundamental {x,y} = {6,1}.
Note: The first case can easily be transformed into the second using the same trick, {u’,v’} = {u√-1, v√-1}.
3. Euler
Theorem: “If there is an odd fundamental soln {u,v} to u2-dv2 = -4, then it leads to the fundamental soln for x2-dy2 = 1 using the transformation {x, y} = {(u4+4u2+1)(u2+2)/2, (u2+3)(u2+1)uv/2}.”
Ex. Let d = 61. Then {u,v} = {39, 5}, and {x,y} = {1766319049, 226153980}.
This was found by combining the Brouncker-Wallis and Cayley theorems, and shows that fundamental solns of u2-dv2 = -4, when odd, are much smaller than those for x2-dy2 = 1 since x is a sixth degree polynomial in u. Historically, Euler used a variant of the identity above (this author modified to make it more aesthetic) to find x2-61y2 = 1 which has the largest solns for d < 100. Parametric fundamental solns to u2-dv2 = -4 with odd {u,v} are,
(n)2 - (4+n2) (1)2 = -4
((1+n)(1+2n+n3))2 - (5+6n+3n2+2n3+n4) (n2+1)2 = -4
with even n for the second. (For ex., for n = 2, it yields d = 61.) Q: Any others?
x = (pu2+2nquv+mnpv2)/(u2-mnv2), y = (qu2+2mpuv+mnqv2)/(u2-mnv2)
and an infinite number of integral x,y can be found by solving u2-mnv2 = ±1. The Paoli-Realis soln is just the special case m=1. Again, without the denominators, the x,y satisfy,
mx2-ny2 = (mp2-nq2)(u2-mnv2)2
Solns for special forms are given by,
S.Realis
(n+2)x2-ny2 = (n+2)p2-nq2
{x, y} = {(n+1)p+nq, (n+2)p+(n+1)q}
x2+nxy-ny2 = p2+npq-nq2
{x, y} = {(n+1)p-nq, (n+2)p-(n+1)q}
II. Transformations
More generally, given an initial soln {p,q} to mp2-nq2 = c, then mx2-ny2 = c where,
PART 5. Pell Equations
I. Complete Solution
II. Transformations
III. Polynomial Parametrizations
IV. Minor updates
I. Complete Solution
C. Hermite
Given an initial soln {p,q} to p2-dq2 = ±1, one can find an infinite number of solns {x,y} by equating,
x2-dy2 = (p2-dq2)k
Using the same technique of equating factors,
x+yÖd = (p+qÖd)k,
x-yÖd = (p-qÖd)k,
we easily solve it as {x, y} = { (ak +a-k)/2, (ak -a-k)/(2Öd) }, where a = p+qÖd, and for the negative case p2-dq2 = -1 only odd powers k should be used. Note that the contribution of a-k diminishes as k increases so effectively are approximated by {x,y} ≈ {ak/2, ak /(2Öd)}.
P.Paoli, S. Realis (all rational solns)
Given an initial soln {p,q} to p2-nq2 = c for some constant c, then,
x2-ny2 = c
where x = (pu2+2nquv+npv2)/(u2-nv2), y = (qu2+2puv+nqv2)/(u2-nv2)
for arbitrary {u,v}. However, if integral x,y is desired, then one can choose {u,v} to solve the Pell eqn u2-nv2 = ±1, with two solns given by (-p,q) and (p,q). Since there is an infinite number of {u,v}, then so for the x,y. The formulas for x,y without their denominators satisfy,
x2-ny2 = (p2-nq2)(u2-nv2)2
Euler
III. Polynomial Parametrizations
The degree of a polynomial soln to x2-dy2 = ±1 will be given by the P(n) defining the variable x.
A. Degrees 1, 2, 3, 4, 6
Deg 1
(y2n+x)2 – (y2n2+2xn+d)y2 = x2-dy2
This identity also shows that for any soln y, parametric or otherwise, to x2-dy2 = c, then there are an infinite number of d' that uses the same y.
Deg 2
(an2+2ny+x)2 – (n2+2bn+d) (an+y)2 = z2,
where a = (x-z)/d, b = (x+z)/y, and x2-dy2 = z2.
Deg 3
(2an3+3abn2+6ny+x)2 – (4n2+4bn+d) (an2+abn+y)2 = x2-dy2
where a = 2(3x-by)/(bd) and b is a root of the cubic b3y-3b2x+3bdy-dx = 0.
Deg 4 (Avanzi and Zannier)
(a2-2b(b2+2b-c))2 – (a2+8bc+16c) (b2+c)2 = -16c3, if a = b2+2b+c
Appropriate choice of b and ±c will result in conventional Pell equations. For {b,c} = {2n, 4} this yields, after removing common factors,
((1+n)(1+2n+n3))2 – (5+6n+3n2+2n3+n4) (n2+1)2 = -4
The case n=0 gives the fundamental soln to x2-5y2 = -4 while n=2 gives Euler’s soln to x2-61y2 = -4. In general, if n is even then x’ is odd, so using Euler’s transformation this gives a parametric fundamental soln to x2-dy2 = 1 for some d. Alternatively, for {b,c} = {2n-1, 1} yields,
(-1+2n+2n2-4n3+4n4)2 – 2(1+2n+2n4) (1-2n+n2)2 = -1
Deg 6 (G. Ricalde)
(8(a3+b3)2+1)2 – ((a+b)2+4) (4(a3+b3)(a2+b2))2 = 1, if b = a+1
Avanzi and Zannier
(2n(1+2n-2n2+8n3-4n4+5n5))2 - (1+4n+4n2+4n4) (1-2n+6n2-4n3+4n4)2 = -1
B. Degrees 5, 7, 11, 13, 17
Solutions to the three equivalent forms,
1. (2pr2-1)2 - pq(2rs)2 = 1,
2. (pr2+qs2)2 - pq(2rs)2 = 1
3. pr2-qs2 = 1
Deg 5 (Avanzi and Zannier)
{p,q,r,s} = {2+3m2+2(-m+m3)n-(1+4m2)n2+2mn3, -1+2mn, -n, 1+mn-n2}
{p,q,r,s} = {-2+3m2+2(m+m3)n-(1-4m2)n2+2mn3, -1+2mn, n, 1+mn+n2}
As well as,
(2+an2)2 – a(1+n)(n(2-n+n2))2 = 4, if a = 1+3n-n2+n3
(2+an2)2 – a(1+n)(n(-2+n+n2))2 = 4, if a = -7-n+3n2+n3
For any n, the {x,y} of the pair above are even so it reduces to x2-dy2 = 1. Setting a = 1+3n-n2+n3 = 0 involves a radical that can be expressed in terms of the Weber class poly for Ö-11, similar to the one for deg 11 which involves Ö-23.
Deg 7 (Avanzi and Zannier)
{p,q,r,s} = {(-1+n2+2n3)/2, 2(-3+2n), -1-2n+2n2, (-1-n+2n3)/2}
Piezas
p = n/4
q = {-4 + (1+2a+3a2-6a3+a4)n - 2a2(1-2a2+a3)n2 + (-1+a)2a4n3}/4
r = 3+3a-a2 + (-1-3a-4a2+3a3)n + a2(2+2a-3a2)n2 + (-1+a)a4n3
s = 1-(1+2a)n+a2n2
A deg-17 soln will result by setting a = bn for some rational b.
Deg 11 (Weber)
{p,q,r,s} = {-1+n2+n3, -5-4n+n2+n3, (-2+n)(1+n)(-2+n2)/2, (-1+n)(-2-2n+n3)/2}
This was found using a modular equation between two elliptic functions at arguments f(w) and f(23w). Note that p,q have discriminant d=23 and p in fact is the inverse of the Weber class poly for Ö-23.
Deg 13 (Piezas)
{p,q,r,s} = {(1-n2)n/4, -4(4-4n+4n3-n5+n7), 2+2n-n2+n4+n5, (1-n2-n3)/4}
This was derived by using a variant of the 2-variable deg-7 soln and likewise setting a = bn for b = -1.
IV. Minor updates
(Update, 12/14/09): Given the fundamental soln {p,q} to x2-dy2 = 1, Gerry Martens defined the following functions:
2G[n] := (p+q√d)n + (p-q√d)n
A[i,j] := (G[i]-1) (G[i+2j+1]+1)/4
B[i,j] := (G[i]+1) (G[i+2j+1]-1)/4
2C[i,j] := (√A[i,j] - √B[i,j] )2 + 1
2D[i,j] := (√A[i,j] + √B[i,j] )2 + 1
then {A,B} and/or {C,D} are squares for certain d.
1. For {A,B} as squares, d = {2, 5, 8, 10, 13, 17, 20, etc}.
2. For {C,D} as squares, d = {2, 7, 8, 14, 23, 31, 34, etc}.
3. For {A,B,C,D} as squares, d = {2, 8, 50, 98, 200, etc}.
Note: Apparently, a necessary but not sufficient condition is that d = u2+v2 for [1], while d = 2m2 for [3]. (End update.)
(Update, 12/21/09): (Piezas) This arose in trying to solve in the rationals,
y4 + 2(u2+auv+bv2)y2 + (u2+v2)4 = z2
Note that this can be made a square if u2+auv+bv2 = (u2+v2)2. Given the quadratic equation, x2+ax+b = 0, and its roots {2x1, 2x2} = {-a+√d, -a-√d}, where d = a2-4b, define the sequence, Pn = 1/d (x1n-x2n).
Theorem: “If b = -1, then an infinite number of solns to the Diophantine equation,
(u2+v2)2 = (u2+auv+bv2)w2
can be given by,
{u,v,w} = {P2m+1, P2m, P4m+1}, and,
{u,v,w} = {P2m+1, -P2m+2, P4m+3}.”
This can be verified in Mathematica after a little manual tweaking.
Example 1. Given x2-x-1 = 0, where {x1, x2} = {(1+√5)/2, (1-√5)/2}, then P(n): = 1/√5 (x1n-x2n) yields the Fibonacci sequence,
P(n): = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…}
so the eqn, (u2+v2)2 = (u2-uv-v2)w2, has solns {u,v,w} = {2,1,5}, {2,-3, 13}, {5, 3, 34}, {5, -8, 89}, etc.
Example 2. Given x2-2x-1 = 0, where {x1, x2} = {1+√2, 1-√2}, then P(n): = 1/√2 (x1n-x2n), after removing the common factor 2, gives the Pell numbers,
P(n): = {1, 2, 5, 12, 29, 70, 169,…}
so (u2+v2)2 = (u2-2uv-v2)w2, has {u,v,w} = {5, 2, 29}, {5,-12, 169}, etc. (End update.)
(Update, 12/23/09): I realized my solns had u2+v2 = w, or (P2m)2 + (P2m+1)2 = P4m+1, which is a known attribute of Fibonacci numbers. Thus, in general, the Diophantine equation,
(u2+v2)2 = (u2+auv+bv2)w2
can be solved by,
{u,v,w} = {p-aq, 2q, u2+v2}, where {p,q} are solns of the Pell equation,
p2-(a2-4b)q2 = 1
generalizing the theorem given in the previous update. (End update.)