Question: 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.

Answer: 
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](http://en.wikipedia.org/wiki/Gaussian_integer) $\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.
Hint :

Use [Brahmagupta–Fibonacci identity](http://en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity).