008: Pell Equations

 

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

 

More generally, given an initial soln {p,q} to mp2-nq2 = c, then mx2-ny2 = c where,

 

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

 

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,

 

(-1+n)2 - (5-2n+n2) (1)2 = -4

((1+n)(1+2n+n3))2 - (5+6n+3n2+2n3+n4) (n2+1)2 = -4

 

for even n = 2m.  (The second, for n = 2, yields d = 61.)  Q: Any others?

 

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. (Though there are exceptions like d = 37, 101, etc.)

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?

   

 

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

 

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

 

For these all known poly solns to x2-dy2 = 1 are of the form,

 

(2pr2-1)2 - pq(2rs)2 = 1,

 

or equivalently, (pr2+qs2)2 - pq(2rs)2 = 1, hence also satisfy pr2-qs2 = 1.  Thus, the variables {p,q,r,s} of the entries below are understood to refer to these equations.

 

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}

 

and,

 

(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,

 

y+ 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-x2nyields 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.)

 

 

 

Previous Page        Next Page  

Comments