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.

I have read this Ask Dr. Math conversation ...

  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
    http://www.alpertron.com.ar/QUAD.HTM 

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.

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/ 

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 
given, how does that reasoning help you conclude that prime factors 
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 
read this Dr. Math conversation on "Quadratic Residues":

  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