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

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
written a couple of very detailed papers describing good methods for
finding all integer solutions to Pell equations and to other quadratic

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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search