Using Gaussian Integers to Solve a Diophantine EquationDate: 05/30/2008 at 16:13:10 From: Colin Subject: Solve x^2+y^2=26819945 in integer solutions Find an integer solution to x^2 + y^2 = 26819945 without trying all values for x or y. You are allowed to use the factorization of 26819945 if necessary. It is easy to solve y^2 - x^2 = 26819945, because that would only require factoring 26819945 = 5 * 41 * 130829, however, I do not know a method to solve this equation. The first thing I did is to try to find integer solutions with a program that just tries all values for x until a perfect square was found: 26819945 - x^2 = y^2. One answer is: 26819945 - 5104*5104 = 877*877. How could I end up with this answer (or other solutions) without trying all integer values for x? Date: 06/26/2008 at 21:24:21 From: Doctor Vogler Subject: Re: Solve x^2+y^2=26819945 in integer solutions Hi Colin, Thanks for writing to Dr. Math. Interesting question! First of all, if your right-hand side were a prime, then you could use the method described in Finding the Two Squares http://mathforum.org/library/drmath/view/63170.html (I've seen another method besides the GCD method, but I'm not sure if it's any better or faster.) There is some more description at a somewhat more elementary level at Decomposition of Primes as the Sum of Two Squares http://mathforum.org/library/drmath/view/70343.html In your case, the difference is that you don't have a prime number. So what happens in this case? I'll remind you that for a prime (which is 1 mod 4), there are exactly eight pairs of integers whose squares sum to the prime. But they're related by switching signs and swapping the numbers. Equivalently, there are exactly eight Gaussian integers whose norm is equal to the prime, and they are related by multiplying by 1, i, -1, and -i, and by taking conjugates. You can get from any one of those eight to all of the others by multiplying by those four Gaussian integers and taking complex conjugates. (You should try this until you understand what's going on.) Well, now you want a Gaussian integer whose norm is some other (composite) number. Just like regular composites are formed by multiplying regular primes together, so too Gaussian composites are formed by multiplying Gaussian primes. When the norm you want (in your case, 26819945) is a product of distinct primes (i.e. no square factors) then every Gaussian composite with this norm is a product of Gaussian primes corresponding to the prime factors of your norm. In other words, to get a Gaussian integer whose norm is 5 * 41 * 130829, you should multiply together a Gaussian prime with norm 5, a Gaussian prime with norm 41, and a Gaussian prime with norm 130829. You can use the method from the first link I referenced to find such primes. The result is that norm(2 + i) = 5, since 2^2 + 1^2 = 5 norm(5 + 4i) = 41, since 5^2 + 4^2 = 41 norm(298 + 205i) = 130829, since 298^2 + 205^2 = 130829. So, for example, we could get one solution to your equation by multiplying together these three: (2 + i)(5 + 4i)(298 + 205i) = -877 + 5104i 877^2 + 5104^2 = 26819945. By chance, this is the same solution you already had. Remember that there are eight such Gaussian integers for each prime, but they are related by multiplying by powers of i and taking complex conjugates. We can do that with each of the three numbers we're multiplying together. But multiplying each number by a power of i will only multiply the result by a power of i, giving essentially the same answer. So this really doesn't make a difference. Similarly, taking the complex conjugate of ALL THREE factors has the effect of taking the complex conjugate of the answer. But taking complex conjugates of SOME of the factors will give you a different answer. So you can get all essentially different solutions by fixing the conjugacy class of one factor and varying the others: (2 + i)(5 + 4i)(298 + 205i) = -877 + 5104i (2 + i)(5 + 4i)(298 - 205i) = 4453 + 2644i (2 + i)(5 - 4i)(298 + 205i) = 4787 + 1976i (2 + i)(5 - 4i)(298 - 205i) = 3557 - 3764i Apart from changing signs and swapping the two numbers, this gives all integer solutions to your equation. 877^2 + 5104^2 = 26819945 4453^2 + 2644^2 = 26819945 4787^2 + 1976^2 = 26819945 3557^2 + 3764^2 = 26819945. 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: 06/30/2008 at 09:28:54 From: Colin Subject: Thank you (Solve x^2+y^2=26819945 in integer solutions) Wow, I never thought I could solve this with Gaussian integers. A very interesting answer, therefore. I learn (and understand) more about math every day. Thank you very much! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/