Finding $a^2 + b^2 =n$.

Question

How do I find the possible sets of two numbers for any positive integer if the sum of squares of the two number is equal to that integer. I mean if $n=a^2+b^2$ $(n,a,b \in N)$.
How can I find the possible sets of $a,b$?

Answer 1

Start with the prime factorization of $n$.

For every prime $p$ with $p\mid n$ with $p\equiv 3\pmod 4$, this prime must occur to an even power $p^{2k}$ in $n$ (or else there are no soutions at all); then all solutions are of the form $(p^kc, p^kd)$ where $(c,d)$ is a solution for $c^2+d^2=\frac n{p^{2k}}$.

For every prime $p$ with $p\equiv 1\pmod 4$, theory tells us that you can find (for small $p$, just use trial and error) a unique solution $a^2+b^2=p$ with $0<a<b$. It is easiest to work with complex numbers: Let $z=a+ib$. If $p^k\mid n$ (but $p^{k+1}\nmid n$), then consider the $k+1$ numbers $$\tag1z^k, z^{k-1}\bar z, z^{k-2}\bar z^2,\ldots, \bar z^k.$$ If $2^k\mid n$ and $2^{k+1}\nmid n$, consider $$\tag2\begin{cases}2^{k/2}&\text{if $k$ is even}\\ 2^{(k-1)/2}\cdot(1+i)&\text{if $k$ is odd}\end{cases} $$ Now if you pick a) one fo the four numbers $$ 1,i,-1,-i$$ and b) the number from $(2)$ and c) for each $p\equiv 1\pmod 3$ one of the numbers in $(1)$, and multiply these together, you obtain a complex number $u+iv$ with $u,v\in \Bbb Z$ and $u^2+v^2=n$. And all solutions are obtainable this way, i.e., by running through all choices made, you generate all solutions.