2
$\begingroup$

I have a number $c$ which is an integer and can be even or odd. It is the hypotenuse of a right angled triangle. How can I find integers $a,b$ such that

$$ a^2 + b^2 = c^2 $$

What would be the complexity of the calculation?

$\endgroup$
  • 1
    $\begingroup$ but the pythagorean triplet that I am looking for is not necessarily a primitive pythagorean triplet. $\endgroup$ – Shadekur Rahman Oct 10 '15 at 13:15
  • $\begingroup$ Not necessarily your problem has a solution. For example for $c = 2,3,6,7,8,9,11,12$ and many more values of $c$ there is no solution. For there to be a solution, your number $c$ must have the form $m (x ^ 2 + y ^ 2)$. $\endgroup$ – Piquito Jun 30 at 23:51
2
$\begingroup$

You may go by trial and error, or through the following lines. Consider the factorization of $c^2$ and separate its members according to them being $4^n$, $p^{2m}$ with $p\equiv 1\pmod{4}$ and $q^{2h}$ with $q\equiv 3\pmod{4}$. Every prime $p\equiv 1\pmod{4}$ splits in $\mathbb{Z}[i]$ and so it can be represented as a sum of two squares in a essentially unique way, $p=a_p^2+b_p^2$. That representation can be recovered with a finite descent that exploits Lagrange's identity: $$ (a_1^2+b_1^2)\cdot(a_2^2+b_2^2) = (a_1 a_2+b_1 b_2)^2 + (a_1 b_2-a_2 b_1)^2. $$ In order to compute $a_p$ and $b_p$ from $p$, we need about $\log(p)$ steps. Have a look at the second part of my answer to this question in order to understand how the descent really works.

Given the representations of every prime $p\equiv 1\pmod{4}$ dividing $c$, we may also recover, through Lagrange's identity, every representation of $c^2$ as a sum of two squares.

$\endgroup$
0
$\begingroup$

You can find one or more triples, given only $C$ if $GCD(A,B,C)=2$ or a perfect square, which includes all primitives and such as $(27,36,45)$. You cannot find those that are otherwise, such as $3,5,6,7,8,10$ times a primitive, e.g. $(45,24,51)=3*(15,8,17)$.

We solve $C=m^2+n^2$ for $n$, and look for positive integers

$$n=\sqrt{C-m^2}\text{ where }{\lceil \sqrt{\frac{C}{2}}\space\rceil\le m\le \lfloor\sqrt{C}\rfloor}$$.

If we want to find one or more triples for $C=145$, then we have $$m_{min}=\lceil \sqrt{\frac{145}{2}}\space\rceil=9\qquad m_{max}=\lfloor\sqrt{145}\rfloor=12$$

If we try $9\le m \le 12$, we find $n\in\mathbb{N}$ only for $\sqrt{145-9^2}=8$ and $\sqrt{145-12^2}=1$

$$f(9,8)=(17,144,145)\qquad f(12,1)=(143,24,145)$$

For $C=1105$, there are $4$ triples; for $C=29$, there is $1$ triple; for $C=31$, there are no triples. If $C=20$, we find $f(4,2)=(12,16,20)=2^2*f(2,1)=2^2*(3,4,5)$. Try the numbers and see for yourself.

$\endgroup$
-3
$\begingroup$

c can be found as

$c=2 r^2 +s^2+2 r s$
$a=2r^2+2 r s$
$b=s^2+2 r s$

Edit Was using x^2+y^2=z^2 variables changed to a^2+b^2=c^2

$\endgroup$
  • $\begingroup$ An answer to this question should find values of $a$ and $b$ in terms of $c$. I don't know why you're computing unrelated quantities from the unknowns $a$ and $b$. $\endgroup$ – epimorphic Jan 26 '16 at 2:51
  • $\begingroup$ Well, how do you find $r$ and $s$ now? And how does this "decomposition" help? $\endgroup$ – epimorphic Jan 26 '16 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.