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