Find the Solution: r^2 + s^2 = c.

Date: 01/28/2003 at 23:47:11
From: Tyrael
Subject: How to find the solution of a^2 + b^2 = c^2?

a, b and c are all positive integers.
given c, find the values of a and b in a^2 + b^2 = c^2.
Is there any systematic approach?

Date: 01/29/2003 at 04:01:20
From: Doctor Jacques
Subject: Re: How to find the solution of a^2 + b^2 = c^2?

Hi Tyrael,

Numbers a, b, c that satisfy the equation a^2 + b^2 = c^2 are called 
"Pythagorean triples." See the Dr. Math FAQ:

   Pythagorean Triples
   http://mathforum.org/dr.math/faq/faq.pythag.triples.html 

This article describes a method for generating all Pythagorean 
triples, as well as several other links on the subject.

However, as I understand, your question is somewhat different - you 
assume that c is given, and ask for a and b.

If you look at the link above, you will see that this essentially 
boils down to finding a solution of:

(*)   r^2 + s^2 = c

This looks like the original equation, but with c instead of c^2.

Now, it can be proved in advanced number theory that, IF c IS PRIME, 
the equation (*) has solutions if and only if c = 2 or c is of the 
form 4n+1 (the "only if" part is rather easy - consider the equation 
modulo 4). Note that c=2 is excluded here, since we already know that 
c must be odd.

Now, assume that c is not prime. Is c is divisible by a square, for 
example, c = (k^2)*c', we can symplify the whole equation by k - in 
the end, you will get a "non-primitive" triple.

If c = c1*c2, we can make use of the following identity:

(**)   (r^2+s^2)(p^2+q^2) = (rp-sq)^2+(rq+sp)^2

to build a solution for c using solutions for c1 and c2:

   r^2 + s^2 = c1^2
   p^2 + q^2 = c2^2
   (rp-sq)^2 + (rq+sp)^2 = (c1*c2)^2 = c^2

The method can therefore be summarized as follows:

1. Remove (and memorize) any square factor from c.

2. Factor the remaining number into primes.

3. If any of the primes is not of the form 4n + 1, there is no 
   solution.

4. For each prime factor of c, find a solution of equation (*). As 
   far as I know, there is no systematic way of doing this - you have 
   to search. However, note that the numbers involved will be much 
   smaller than the original c^2.

5. Combine the solutions using the technique shown in equation (**). 
   Note that, by interchanging p and q, you will find more than one 
   solution.

6. Include the square factors removed at step (1)

7. Compute the solutions of the orginal equation (i. e. a and b) 
   using the technique described in the link above.

For example, let us try to solve:

   a^2 + b^2 = 65^2

We see that 65 = 5*13, and both factors are of the form 4n+1.

By trial and error, we find:
   5 = 1^2 + 2^2
  13 = 2^2 + 3^2

Combining these using equation (**), we find:

  65 = (1*2-2*3)^2 + (1*3+2*2)^2 = 4^2 + 7^2

which gives r = 7 and s = 4. (Note that, by interchanging the two 
terms in the first equation, we would find another solution, namely
65 = 1^2 + 8^2).

Going back to r = 7 and s = 4, we use the technique shown in the 
article to find:

  a = r^2 - s^2 = 49 - 16 = 33
  b = 2*r*s = 2*7*4 = 56

and we verify that

  65^2 = 33^2 + 56^2


However, I have only told you part of the story. The answer I gave you 
is focused on finding primitive solutions, but other solutions are 
also important.

If we have any solution of

    c^2 = a^2 + b^2

by multiplying by k^2, we can find a solution of

   (ck)^2 = (ak)^2 + (bk)^2

For example, from the solution

   3^2 + 4^2 = 5^2

we can find, by multiplying by 3^2:

   9^2 + 12^2 = 15^2

If c has any factor of the form 4n+3 (or 2), this is the only way 
these factors can be used.

Even for factors of the form 4n+1, in addition to the method given by 
equation (**) in my previous answer, you may also combine them by 
simple multiplication.

For example, I gave you the solution:

   65^2 = 33^2 + 56^2

But you can also find other solutions. For example, starting with

   5^2 = 3^2 + 4^2

and multiplying by 13^2, we find another solution:

   65^2 = 39^2 + 52^2

We can also start with

   13^2 = 12^2 + 5^2

and get, by multiplication by 5^2 :

   65^2 = 60^2 + 25^2

The complete method should be:

1. Remove from c any (possibly repeated) prime factor of the form 
   4n+3 or 2. These factors will appear as common factors of a, b, and 
   c in the final solution.

2. If there is nothing left, there is no solution.

3. Otherwise, all remaining prime factors are of the form 4n+1. For 
   each such factor p, find a solution of

    r^2 + s^2 = p

4. Combine those solutions as explained in the previous answer, or by 
   taking one solution and multiplying by another prime factor, as 
   shown above.

5. Include the factors removed at step 1.

The condition for a solution to exist is that c must have at least 
one prime factor of the form 4n+1.

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