# sum of two squares $n = a^2 + b^2$ where n is not prime

From, Fermat's theorem on sums of two squares we know that if $p$ is prime and $p$ mod $m$ == $1$ then $p$ can be represent as sum of two squares , what if $p$ is not prime. For example $100 = 8^2 + 6^2$

Only I have to know that, can $p$ represent as a sum of tow squares or not where $p$ is not a prime number ?

Hint:-

If $m$, $n$ be two numbers which can be represented as a sum of two squares, so is $mn$.

Proof

Let $m=a^2+b^2$ and $n=c^2+d^2$. Then \begin{align}mn&=\left(a^2+b^2\right)\left(c^2+d^2\right)\\&=a^2c^2+a^2d^2+b^2c^2+b^2d^2\\&=\left(a^2c^2+2abcd++b^2d^2\right)+\left(a^2d^2-2abcd+b^2c^2\right)\\&=\left(ac+bd\right)^2+\left(ad-bc\right)^2\end{align}

Let us consider the four possible cases:

$i:(2m)^2+(2n)^2=4(m^2+n^2)\equiv0\pmod4$

$ii,iii:(2m)^2+(2n+1)^2,(2m+1)^2+(2n)^2\equiv1\pmod4$

$iv:(2m+1)^2+(2n+1)^2\equiv2\pmod4$

So, if a given number is $\equiv3\pmod4,$ there is simply no solution

If a given number is $\equiv0\pmod4,$(case $i$) like $100,$ we can straight away take out $4$ repeatedly as long as the quotient is divisible by $4$

If a given number is $\equiv2\pmod4,$ (case $iv$)

$(2m+1)^2+(2n+1)^2=2\{(m+n+1)^2+(m-n)^2\}$

we can take out $2$

If a given number$(N)$ is $\equiv1\pmod4,$ (case $ii/iii$)

clearly if prime $p\equiv3\pmod4,p\mid N$ and $p^k||N,k$ must be even as $N\equiv1\pmod4$

Take out all such primes with their highest powers that divides $N$