Which integers can be expressed as a sum of squares of two coprime integers? I want to find integers $z=a^2+b^2$ with $\gcd(a,b)=1$.  Clearly all prime numbers of the form $4k+1$ are such numbers, but what other composite numbers also enjoy this property?  e.g. $74=5^2+7^2$, $625=7^2+24^2$.  Please answer.
 A: All integers $z$ which are products of primes of the form $4k+1$, optionally multiplied by a single copy of $2$, can be expressed as $a^2 + b^2$ with $\gcd(a,b) = 1$.
You basically uses the fact the Gaussian integers $\mathbb{Z}[i]$ is an unique factorization domain and there are 3 types of primes in $\mathbb{Z}[i]$:


*

*$1+i$ 

*$a+ib$, $a-ib$ where $a^2 + b^2 \in \mathbb{Z}$ is a prime of the form $4k+1$

*$p \in \mathbb{Z}$ is a prime of the form $4k + 3$.


If you number $z$ can be factored as $2^{e}\prod_{j} p_{j}^{e_j}$ where
$e = 0 \text{ or } 1$, $p_j = a_j^2 + b_j^2$ are primes of the form $4k+1$,
then $z = a^2 + b^2$ where $a$ and $b$ are defined by:
$$a + i b = (1 + i)^{e}\prod_j (a_{j} + i b_{j})^{e_j}$$
Since $\mathbb{Z}[i]$ is an UFD, it is not hard to verify $\gcd(a,b) = 1$.
The only case that is not that obvious is when your $z$ is even. In that case,
only one copy of 2 is allowed.
This annoyance is caused by the fact $1 + i$ and $1 - i$ are equivalent primes in $\mathbb{Z}[i]$, i.e. $1 + i$ differs from $1 - i$ by a factor $i$ which is a unit of $\mathbb{Z}[i]$. In contrast, if you break a prime $p_j \in \mathbb{Z}$ of the form $4k+1$ into $(a_j + i b_j) (a_j - i b_j)$, the two prime factors of it in $\mathbb{Z}[i]$ $a_j + i b_j$ and $a_j - i b_j$ are inequivalent in $\mathbb{Z}[i]$.
In any UFD, when you express a number as a product of its prime factors. The factorization is unique only up to units of the UFD. That's why the prime factor $2$ in $z$ need special treatment.
A: Hint :
Use Brahmagupta–Fibonacci identity.
