Efficiently finding all sums of squares that sum to a given number.

76 Views Asked by At

Lately I've been trying to solve a problem that asks me to find all solutions to $N = x^2 + y^2$, where $N$ is squarefree, and all its prime factors are of the form $4k + 1$. Using the Diophantus identity I know how to get solutions to $N = x^2 + y^2$ by using the solutions to $p = a^2 + b^2$, where $p$ is each of the prime factors of $N$. I'm more concerned on whether these are all the possible solutions.

In other words, I would like to know whether there is an $N = rs$, where $r$, $s$ are of the form $4k + 1$, such that $N = x^2 + y^2$, but none of the integer solutions to $r = a^2 + b^2$, $s = c^2 + d^2$ generate $x$, $y$ using the Diophantus identity.