Associated Topics || Dr. Math Home || Search Dr. Math

### Counting Solutions of Quadratic Diophantine Equations

```Date: 02/21/2009 at 09:09:22
From: Harsha
Subject: Counting solutions of Quadratic Diophantine equation

Hi,

I am wondering if there is a way to count the number of integer
solutions of

x^2 + y^2 = 2*N^2,

where N is an even integer.

I am only interested in those N for which the number of solutions is
some given number -- say, N = 108.

http://mathforum.org/library/drmath/view/55988.html

... and some related links; but all of them actually solve the
problem first in order to then count the number of solutions.  I am
wondering if it is possible to count the number of solutions for some
N without explicitly finding all solutions to the equation.

For example, the Dr. Math conversation above gives the solution when

B^2 - 4AC = k^2.

Since we have A = 1, B = 0 and C = 1 here, the left-hand side equals
-4 -- which cannot be k^2 for any k.  I need to solve the elliptical
case, when

B^2 - 4AC < 0,

as given in Dario Alpern's

Generic Two integer variable equation solver

It is quite easy to do that by solving the quadratic in x to get the
range of x values and then taking integer values of x in that range
to solve for y.  But is it possible to do this better, if all I am
interested in is the number of solutions, and not the actual
solutions themselves?

```

```
Date: 02/21/2009 at 15:26:37
From: Doctor Vogler
Subject: Re: Counting solutions of Quadratic Diophantine equation

Hi Harsha,

Thanks for writing to Dr. Math.

You can count the number of solutions by factoring N.  Then you can
use the Gaussian integer method described at ...

http://mathforum.org/library/drmath/view/72066.html

... to get a formula for the number of solutions in terms of the
exponents of the primes in the prime factorization of N, which are 1
mod 4; and in terms of the exponents of the primes, which are 3 mod 4
(and the power of 2 in N).

Now, once you have factored N, you would only have to apply the
Gaussian GCD to actually list off all of the solutions.  So it turns
out that counting them isn't really much easier than finding them.

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/

```

```
Date: 02/21/2009 at 22:27:30
From: Harsha
Subject: Counting solutions of Quadratic Diophantine equation

Thanks, Dr. Vogler.

I understand the example shown in the link.  I see how it takes the
right-hand side of the equation

x^2 + y^2 = 26819945

and decomposes 26819945 into prime factors, then finds out the
Gaussian primes for each of these primes before continuing further.
In this example,

26819945 = 5 * 41 * 130829,

where all three prime factors are 1 mod 4.

So that makes me wonder how one proceeds when this is not the case.
For example, imagine that we had the equation

x^2 + y^2 = 10000

Here, 10000 = 2^4 * 5^4.  5 is 1 mod 4, but 2 is not.

Also, I didn't understand when you said earlier that "the exponents
of the primes ... are 3 mod 4 (and the power of 2 in N)."  Could you
please explain this a bit more?

In general I would like to solve for integers x and y and any N in

x^2 + y^2 = 2*N^2

Thanks for the pointers.

```

```
Date: 02/22/2009 at 23:54:03
From: Doctor Vogler
Subject: Re: Counting solutions of Quadratic Diophantine equation

Hi Harsha,

Good questions, all.

It turns out that the prime numbers that are 1 mod 4 always split
into a product of two Gaussian primes, such as

17 = (4 + i)(4 - i),

but prime numbers that are 3 mod 4 are "inert," meaning that they are
still prime in the ring of Gaussian integers.  The prime 2 ramifies,
because it is the square of the prime 1 + i (times the unit -i).  So
when you have the prime factorization of 2N^2 as an integer, you can
separate the primes into those three categories:

(1) 2 (the only prime that is ramified)
(2) 1 mod 4 primes (the ones that split)
(3) 3 mod 4 primes (the ones that are inert)

Then different things can happen according to the categories that the
primes fall in.  Remember that we are considering how 2N^2 factors
into

(x + yi)(x - yi),

and it is important that the second factor (x - yi) is the complex
conjugate of the first (x + yi), as this strongly limits how the
primes can be arranged.

The possibilities fall into three different categories:

Category 1. If 2^k is the largest power of 2 dividing the right-hand
side -- and in your case, with 2N^2, k will be odd, but I won't
assume that in this explanation -- then this means that

(x + yi)(x - yi) is divisible by (1 + i)^(2k).

But since the second factor is the conjugate of the first, the powers
must be divided evenly.  So

(1 + i)^k divides x + yi,

and

(1 + i)^k divides x - yi.

Category 2. If p^k is the largest power of p (for a prime p which is
1 mod 4) dividing the right-hand side, and the prime p splits into
Gaussian primes as

p = (a + bi)(a - bi),

then for some powers r and s, the quantity x + yi will be divisible
by the product

(a + bi)^r * (a - bi)^s

Similarly, the conjugate x - yi will be divisible by the same thing,
but with the exponents (r and s) switched.

The two exponents must add to k:  r + s = k.  So there is some number
r (between 0 and k, inclusive) such that

(a + bi) divides x + yi exactly r times,

and

(a - bi) divides x + yi exactly k - r times.

And there are k + 1 ways that this prime can be divided among the two
factors x + yi and x - yi.

Category 3. If p^k is the largest power of p (for a prime p which is
3 mod 4) dividing the right-hand side, then k *MUST* be even for any
solutions to exist at all.  If k is even, then x + yi will be
divisible by p^(k/2), as must x - yi -- and neither will be divisible
by p^(k/2 + 1).  This is equivalent to saying that the integers x and
y are each divisible by p^(k/2).  (And at least one of them will not
be divisible by p^(k/2 + 1).)

Does that clear things up for you?

Now, it looks like you don't get any options for primes in categories
1 or 3, so all you have to do is find the exponents (in 2N^2) of
primes that are 1 mod 4.  Then add one to each such exponent and
multiply them together.  (You might like to throw in another constant
factor, which will depend on whether you consider changing signs or
swapping x and y to give "different" solutions.)

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 02/23/2009 at 21:52:10
From: Harsha
Subject: Counting solutions of Quadratic Diophantine equation

Hi Doctor Vogler,

Thanks for the clarifications.

While it was very detailed, I think I now have more questions on what
you have written, perhaps because I don't have the necessary math
background in number theory.  I think I would help myself best if I
read a recommended textbook on this material.  Would you kindly
recommend a good book, or preferably online material, to read and
work through some examples?  I have a computer science background
with as much math as one would learn in an engineering degree; and am
looking to learn about algorithms to solve diophantine equations of
the kind mentioned here or some variants, such as

ax^2 + by^2 = c,

where a, b, c are integers, and we need integer solutions for x and y.

In the meantime ... even if I accept the facts of category 1 as
in 2N^2 don't contribute to any solutions of the original equation?
And similarly with category 3?

Thanks
Harsha

```

```

Date: 02/24/2009 at 00:08:49
From: Doctor Vogler
Subject: Re: Counting solutions of Quadratic Diophantine equation

Hi Harsha,

Perhaps an example would help.

Let's suppose that N = 70 = 2*5*7.  (That way, N has one prime from
each category.)  Then in the Gaussian integers, 2N^2 factors as

N = 2^3 * 5^2 * 7^2
= i (1 + i)^6 * (2 + i)^2 * (2 - i)^2 * 7^2.

The initial i can pretty much be ignored, as it is a unit; and (like
-1) can be freely passed around from prime to prime without really
changing the factorization significantly.  In our case, units only
change the order and sign of our final variables x and y.

Okay, now we need to factor the left-hand side x^2 + y^2 as

(x + yi)(x - yi).

Thus, some of those factors of 2N^2 will belong to x + yi, and the
rest will belong to x - yi.  Since the one is conjugate to the other,
their factorizations will also be conjugate.  (Note that the
conjugate to 1 + i is 1 - i, which is just 1 + i times the unit -i.)
If we disregard units, then x + yi must have some factors 1 + i, and
x - yi will have the conjugate of those factors, which will be a unit
times the same power of 1 + i.  So they must each have 3 factors of 1
+ i.

x + yi :  (1 + i)^3
x - yi :  (1 + i)^3

Similarly, the conjugate of 7 is 7, so each must have one factor of 7.

x + yi :  (1 + i)^3 * 7
x - yi :  (1 + i)^3 * 7

But the other factor presents us with some choices.  We could have
several different options -- namely,

(1)
x + yi :  (1 + i)^3 * (2 + i)^2 * 7
x - yi :  (1 + i)^3 * (2 - i)^2 * 7

(2)
x + yi :  (1 + i)^3 * (2 + i) * (2 - i) * 7
x - yi :  (1 + i)^3 * (2 + i) * (2 - i) * 7

(3)
x + yi :  (1 + i)^3 * (2 - i)^2 * 7
x - yi :  (1 + i)^3 * (2 + i)^2 * 7

Let's multiply out the three possibilities:

(1)
x + yi = -98 - 14i

(2)
x + yi = -70 + 70i

(3)
x + yi =  14 + 98i

It's easy to check that

98^2 + 14^2 = 70^2 + 70^2 = 9800.

In the end, then, there was only one thing we could do with the
factors of 2 and with the factors that were 3 mod 4; but there were
three things we could do with the factor that was 1 mod 4, since its
exponent was 2 (and 3 = 2 + 1; add 1 to the exponent).  So there are
3 different numbers x + yi (up to units) which have

x^2 + y^2 = 2N^2.

Since there are 4 units (1, i, -1, -i), there are 12 different numbers
x + yi which have

x^2 + y^2 = 2N^2,

namely

(98, 14)
(-98, 14)
(98, -14)
(-98, -14)
(14, 98)
(-14, 98)
(14, -98)
(-14, -98)
(70, 70)
(-70, 70)
(70, -70)
(-70, -70)

So you should add 1 to each exponent of a prime which is 1 mod 4,
multiply them all together, and then multiply by 4.

If you don't want to consider as different those answers that you can
derive by changing signs or swapping x and y, then you have to figure
out how many of these come in sets of 8 and how many come in sets of
4.  If the right hand side is a square, then there will be one set of
4 where one of the variables is zero (which doesn't change when you
negate it). And if the right hand side is twice a square (as in your
case), then there will be one set of 4 where the two variables have
the same absolute value (so swapping x and y doesn't do anything).
So you should add 1 to each exponent of a prime which is 1 mod 4,
multiply them all together, then subtract 1 if all exponents are even
-- except possibly the exponent of 2 -- and divide by 2.

Does that clear things up for you?

For a good book on this topic and on algebraic number theory more
generally, I would recommend "Number Fields" by Marcus.  It might be
a little much for a non-mathematician who hasn't done much abstract
algebra or modern algebra.  If that's your case, then I would
recommend any of several books called something like "Elementary
Number Theory" or "Introduction to Number Theory."  I don't have a
preference for any such.

For solving second-degree Diophantine equations in two variables, I'd
like to refer you to John Robertson's home page, where he has some
very nice papers on solving just this kind of problem:

http://www.jpr2718.org/

Whereas the Dr. Math archives cover some special cases (with complete
solutions for the easier ones), Robertson's papers describe solutions
for all cases.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 02/24/2009 at 10:31:07
From: Harsha
Subject: Counting solutions of Quadratic Diophantine equation

Hi Doctor Vogler,

The example was very helpful.  I understand it well now.

The only thing I feel I still need to learn is how to factorize
primes of the form 4n + 1 into Gaussian primes.  I think I should

http://mathforum.org/library/drmath/view/63170.html

Thanks for your help.  I really appreciate it very much and I learned
a lot.  This would have taken me days to learn from a textbook.

Thanks
Harsha
```
Associated Topics:
College Modern Algebra

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