Finding Pythagorean triplet given the hypotenuse

Question

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?

Answer 1

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.

Answer 2

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