Using Gaussian Integers to Solve a Diophantine Equation

Date: 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!