Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Solving Quadratic Diophantine and Pell Equations

Date: 05/04/2005 at 10:40:04
From: Deden 
Subject: NumberTheory

Dear Dr. Math,

Would you show me how to solve Diophantine equations that have the
form a*x^2 + b*y^2 = z^2, with a, b, and z given?



Date: 05/04/2005 at 18:38:03
From: Doctor Vogler
Subject: Re: NumberTheory

Hi Deden,

Thanks for writing to Dr. Math.  So your equation is

  a*x^2 + b*y^2 = z^2.

If a and b are given, and you want integer solutions in x, y, and z,
then that is an easier question, because it means you really want to
find rational solutions to

  a(x/z)^2 + b(y/z)^2 = 1,

and you can learn about methods to find all rational solutions to an
equation at

  Rational Solutions to Two Variable Quadratic Equation
    http://mathforum.org/library/drmath/view/65319.html 

But if, as you said, a, b, and z are given, and you want to find
integer solutions in x and y, then it is slightly more complicated,
but it can still be done.  More generally, given a, b, and c, you can
find integer solutions to

  a*x^2 + b*y^2 = c.

(For your equation, just take c = z^2.  The fact that it's a square
doesn't change much.)  There are a few different cases according to
what a, b, and c are.


Case 1:  sign(a) = sign(b) = -sign(c).

If a and b have the same sign (that is, both negative or both 
positive), then the left side of the equation will also have that 
sign, since x^2 and y^2 can never be negative.  But if the right side
(c) has a different sign, then there cannot be any solutions.

Example:  x^2 + y^2 = -1.


Case 2:  sign(a) = sign(b) = sign(c).

If a, b, and c all have the same sign, then there are finitely many
solutions.  If all three are negative, then we can multiply both sides
of the equation by -1 and then all three will be positive.  Now
suppose that all three are positive.  Then since b*y^2 is greater than
or equal to zero, that means

  a*x^2 <= c
  x^2 <= c/a.

So all you have to do is check all of the integers from 0 up to the
square root of c/a.  For each of those numbers x, check if

  y^2 = (c - a*x^2)/b

is both an integer and the square of an integer.

Example:  x^2 + 5y^2 = 14
Then y^2 <= 14/5 = 2.8.  So we check y=0 and y=1, and only y=1 has a
solution.  So the solutions are

  (-3, -1), (3, -1), (-3, 1), (3, 1).

You can also narrow down your search by using modular arithmetic (what
values can x mod b have?).

Example:  7x^2 + 2y^2 = 46
Then x^2 <= 46/7 = 6.5..., but also 7x^2 must be even, and so x must
also be even.  So we check x = 0 and x = 2, and only x = 2 works.  So 
the solutions are

  (-2, -3), (2, -3), (-2, 3), (2, 3).

Furthermore, quadratic reciprocity might allow you to determine very
quickly that there are no solutions (if it is true that there are no
solutions).

Example:  7x^2 + 3y^2 = 692
Looking at this equation mod 3, we get x^2 = 2 (mod 3), which is
impossible.


Case 3:  -ab is a square

If you have

  -ab = m^2,

then you can factor the left side.  First multiply both sides of the
equation by a:

  a^2*x^2 + ab*y^2 = ac

and then change ab to -m^2 and factor:

   a^2*x^2 - m^2*y^2 = ac
  (ax + my)(ax - my) = ac.

In this case, since ax + my and ax - my are both integers, each must
be a factor of ac.  So you can factor ac, make a list of all of its
factors (and make sure that every number appears once as a positive
and once as a negative), and then for each one, let ax + my be the
factor F and ax - my be the corresponding factor G = ac/(ax + my). 
Then you can solve for x and y:

  ax + my = F
  ax - my = G
  x = (F + G)/(2a)
  y = (F - G)/(2m)

and you throw away those solutions that don't give you integers.

Example:  x^2 - y^2 = 10
We factor this as (x - y)(x + y) = 10, and we list off all factors of
10, namely

  -10, -5, -2, -1, 1, 2, 5, 10,

and for each we get

  x = -11/2, -7/2, -7/2, -11/2, 11/2, 7/2, 7/2, 11/2,

but none of these are integers, so there are no solutions.


Case 4:  -ab is positive, but not a square

This is the most difficult, or most complicated case.  First I should
discuss one particular case, namely when a=1, and c=1, and b is
negative, but -b is not a square.  Then we generally write d = -b, so
that the equation is

  x^2 - d*y^2 = 1.

This equation is called Pell's Equation.  It takes some work to prove
that this equation will have infinitely many solutions, and all of
them are related in a simple way.  In fact, there are two ways to show
the relation.  The idea is to find, first, the smallest positive
solution (meaning NOT x = 1, y = 0) and call this solution (r, s), so 
that

  r^2 - d*s^2 = 1.

Then all solutions can be written in the form

  x + y*sqrt(d) = + or - (r + s*sqrt(d))^k

for an integer k.  In fact, changing the sign of k amounts to changing
the sign of y, and changing the "+ or -" amounts to changing the signs
of both x and y.  You can also write this as a recurrence; the first
solutions are

  (1, 0)

and then

  (r, s),

and

  (r^2 + ds^2, 2rs),

and then the recurrence continues infinitely, in both directions,
where the solution that comes AFTER (x, y) is

  (rx + dsy, sx + ry),

and the one that comes BEFORE (x, y) is

  (rx - dsy, -sx + ry).

As I mentioned, proving this takes some work.  And the situation only
gets more complicated in the more general case when a is not 1, and c
is not 1.

If c is not 1 (but a = 1 still), then there may be several, although
always finitely many "small solutions" (like (1, 0)) that start the
recurrence, and then the recurrence still uses the same rule, where

  (rx - dsy, -sx + ry)

becomes

  (x, y),

which becomes

  (rx + dsy, sx + ry),

where r and s are the smallest solution for the associated Pell
Equation with c=1.  In the other form, this means that

  x + y*sqrt(d) = (x0 + y0*sqrt(d))*(r + s*sqrt(d))^k

where (r, s) is the smallest positive solution to

  r^2 - d*s^2 = 1,

and there are finitely many choices of (x0, y0) to choose from.

Finally, when a is not 1, then generally we still multiply the
equation by a, getting

  (ax)^2 - (-ab)*y^2 = ac,

and then we solve the equation for integers in (ax, y), where d = -ab,
and then we throw away the solutions that don't have ax divisible by a.

I deliberately tried to keep this discussion short, since it's a
complicated topic, so if you want more details, then I will refer you
to several places where you can learn more about Pell Equations, and
quadratic Diophantine equations.  There are a couple of helpful
answers from our own archives, which you can find by searching our
archives for "Pell equation."  Then there is the MathWorld site on the
subject at

    http://mathworld.wolfram.com/PellEquation.html 

You can certainly find much more information on the Internet by
searching Google for "Pell equation," but I would like to point out
two more good resources.  One is a short paper written by a 
mathematician named Lenstra, which can be found at

    http://www.ams.org/notices/200202/200202-toc.html 

It is a very interesting paper that touches only lightly on many
different aspects of Pell equations.  It's good reading, and not too
hard to read.  The other is the home page of John Robertson, who has
written a couple of very detailed papers describing good methods for
finding all integer solutions to Pell equations and to other quadratic
Diophantine equations.  This page is at

    http://hometown.aol.com/jpr2718/ 

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/