# List solutions of $x^{2} + y^{2} = z$ ignoring signs and order ($x > 0$ and $y > 0$). [duplicate]

This question already has an answer here:

I know there is a known way to count the number of solutions of $x^2 + y^2 = z$, Sum of squares. Is there an efficient way to enumerate the solutions ignoring sign and order?

## marked as duplicate by kingW3, Glorfindel, Ken Duna, levap, NamasteAug 15 '17 at 20:21

Conventionally we write $r_2(n)$ for the number of representations of $n$ as a sum of two squares where we do take signs and order into consideration.
If $n$ has no representations as $x^2+y^2$ with $x^2=0$, $y^2=0$ or $x^2=y^2$, the representations come in packets of eight, where adjusting signs and orders keeps you in the same packet so the number of representations ignoring order/signs is $r_2(n)/8$.
If $n$ is a square or twice a square, then we need to consider representations $x^2+0^2$, $0^2+y^2$ and $x^2+x^2$ etc. The answer in this case will be $(r_2(n)+4)/8$.
• @vamsikal As far as I am aware, "count" and "enumerate" are synonyms. If you want to generate or list the solutions, this is reasonably easy if one has the prime factorisation of $n$. – Lord Shark the Unknown Aug 15 '17 at 6:19
• I want to list/generate all the solutions, and it is easy to factorize $z$, can you point me to a reference to the algorithm that generates/lists the solutions. – vamsikal Aug 15 '17 at 6:21
HINT.-The calculation is based on the following: every odd prime is of the form $4n\pm 1$. Those of the form $4n + 1$ and the even prime $2 = 1 + 1$ are sum of two squares but those of the form $4n-1$ are not. In addition, the sums of two squares are stable for multiplication: $$(a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(ad\mp bc)^2$$ You apply this to the canonical product in your link $$n=2^{a_0}\prod p_1^{2a_i}\prod q_j^{b_j}$$ where the primes $p_i=4n_i-1$ need to be with even exponent in order you can express n as a sum of two squares.