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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum