Integers that are sums of two squares

Question

It is easy to decide if a given integer $n$ is the sum of two squares, and in fact there is a simple formula (based on the prime factorization) to compute the number of ways that $n$ can be written as the sum of two squares (see for example Wikipedia). But I cannot find a discussion of how two different representations will be related. In other words, suppose that we find a representation $a^2+b^2=n$. Is there a way to find another pair $(c,d)$ from $(a,b)$ so that $n=c^2+d^2$? I am thinking of something similar to the solutions of $ax-by=1$ for relatively prime $a,b$. It is easy to see that all other solutions will be of the form $(x+bk, y+ak)$, where $k$ is any integer. Is there something similar for the sum of two squares?

Answer 1

It's easy, if factorization in the Gaussian integers is easy. E.g., from $65=8^2+1^2$ you get $65=(8+i)(8-i)$. Now if you can factor $8+i=(2-i)(3+2i)$, whence $8-i=(2+i)(3-2i)$, then you can calculate $(2+i)(3+2i)=4+7i$, yielding $65=4^2+7^2$.