I refer to this question.
Given a perfect square, can you prove that it is a sum of two perfect squares?
I recently saw this:
Let $p,q$ be primes. $p_i \equiv 1 \pmod 4$ and $q_i \equiv 3 \pmod 4$.
$N=p_1^{a_1}p_2^{a_2}\cdots q_1^{b_1}q_2^{b_2}\cdots$
$N$ can be written as sum of 2 squares iff all $b$ are even.
I used an identity that can multiply two numbers that can be written as sum of two perfect squares into a number that can be written as two perfect squares. And I have proved that the $p$ part can be written as two squares. Hence it is left to prove that the $q$ part can be written as sum of two squares.
Any help is appreciated. Thanks.
Best Answer
This is the outline of the proof found in the book "Proofs from THE BOOK" (P.17-22) by Aigner, Martin, Ziegler, Günter M. It is too long to put in a comment so I put it here. Please do not vote for it.
Lemma 1. For primes $p=4m+1$ the equation $s^2\equiv -1$ (mod $p$) has two solutions $s\in\{1,2,\dots,p-1\}$, for $p=2$ there is one such solution, while for primes of the form $4m+3$ there is no solution
Lemma 2. No number $n=4m+3$ is a sum of two squares.
Proposition. Every prime of the form $p=4m+1$ is a sum of two squares, that is, it can be written as $p=x^2+y^2$ for some natural numbers $x,y\in\mathbb{N}$
Theorem. A natural number $n$ can be represented as a sum of two squares if and only if every prime factor of the form $p=4m+3$ appears with an even exponent in the prime decomposition of $n$.