[proofplan]
We prove the obstruction first: a prime $q \equiv 3 \pmod 4$ dividing a [sum of two squares](/theorems/1725) must divide both summands, so its exponent in any represented integer drops by two at a time. This forces every such exponent to be even. Conversely, we show that the represented integers are closed under multiplication by the two-square product identity; since $2$, every prime $p \equiv 1 \pmod 4$, and every even power $q^{2r}$ with $q \equiv 3 \pmod 4$ are represented, their product is represented.
[/proofplan]
[step:Show that primes congruent to $3$ modulo $4$ divide both entries of any represented multiple]
Let $q$ be a prime with $q \equiv 3 \pmod 4$, and let $x,y \in \mathbb{Z}$ satisfy
\begin{align*}
q \mid x^2 + y^2.
\end{align*}
We claim that $q \mid x$ and $q \mid y$.
Suppose first that $q \nmid y$. Let $\bar{y}^{-1}$ denote the inverse of the residue class of $y$ in the field $\mathbb{Z}/q\mathbb{Z}$, and define
\begin{align*}
t \equiv x\bar{y}^{-1} \pmod q.
\end{align*}
Then
\begin{align*}
t^2 \equiv x^2 y^{-2} \equiv -1 \pmod q.
\end{align*}
By Fermat's little theorem (citing a result not yet in the wiki: Fermat's little theorem), since $q \nmid t$, we have
\begin{align*}
t^{q-1} \equiv 1 \pmod q.
\end{align*}
On the other hand, because $q \equiv 3 \pmod 4$, the integer $(q-1)/2$ is odd, so
\begin{align*}
t^{q-1} = (t^2)^{(q-1)/2} \equiv (-1)^{(q-1)/2} \equiv -1 \pmod q.
\end{align*}
This contradiction shows that $q \mid y$. Substituting this into $q \mid x^2 + y^2$ gives $q \mid x^2$, hence $q \mid x$ because $q$ is prime. The same conclusion follows if the assumption $q \nmid x$ is used instead, so necessarily $q \mid x$ and $q \mid y$.
[guided]
The key obstruction is that $-1$ is not a quadratic residue modulo a prime $q \equiv 3 \pmod 4$. We verify that obstruction directly.
Assume $q \mid x^2 + y^2$. If $q \nmid y$, then the residue class of $y$ is invertible in $\mathbb{Z}/q\mathbb{Z}$. Let $\bar{y}^{-1}$ be its inverse and define the residue class
\begin{align*}
t \equiv x\bar{y}^{-1} \pmod q.
\end{align*}
Multiplying the congruence $x^2 + y^2 \equiv 0 \pmod q$ by $y^{-2}$ gives
\begin{align*}
t^2 \equiv x^2 y^{-2} \equiv -1 \pmod q.
\end{align*}
Since $t^2 \equiv -1 \pmod q$, the class $t$ is nonzero modulo $q$. Fermat's little theorem (citing a result not yet in the wiki: Fermat's little theorem) therefore gives
\begin{align*}
t^{q-1} \equiv 1 \pmod q.
\end{align*}
But $q \equiv 3 \pmod 4$ means $(q-1)/2$ is odd. Raising $t^2 \equiv -1 \pmod q$ to the power $(q-1)/2$ gives
\begin{align*}
t^{q-1} = (t^2)^{(q-1)/2} \equiv (-1)^{(q-1)/2} \equiv -1 \pmod q.
\end{align*}
This contradicts $t^{q-1} \equiv 1 \pmod q$. Hence $q \mid y$. Returning to the original divisibility,
\begin{align*}
q \mid x^2 + y^2
\end{align*}
and $q \mid y$ imply $q \mid x^2$. Since $q$ is prime, Euclid's lemma gives $q \mid x$. Thus any prime $q \equiv 3 \pmod 4$ dividing a sum of two squares divides both entries of the representation.
[/guided]
[/step]
[step:Deduce that each prime congruent to $3$ modulo $4$ occurs to even exponent]
Assume that
\begin{align*}
n = a^2 + b^2
\end{align*}
for some $a,b \in \mathbb{Z}$. Fix a prime $q \equiv 3 \pmod 4$, and write
\begin{align*}
n = q^{\beta_q}m
\end{align*}
with $m \in \mathbb{N}$ and $q \nmid m$.
If $\beta_q = 0$, there is nothing to prove. Suppose $\beta_q \geq 1$. Since $q \mid n = a^2+b^2$, the previous step gives $a = qa_1$ and $b = qb_1$ for some $a_1,b_1 \in \mathbb{Z}$. Therefore
\begin{align*}
n = q^2(a_1^2+b_1^2).
\end{align*}
In particular, $q^2 \mid n$ and
\begin{align*}
\frac{n}{q^2} = a_1^2+b_1^2.
\end{align*}
Repeating this argument while the remaining quotient is divisible by $q$, we see that a representation loses powers of $q$ only in pairs.
If $\beta_q$ were odd, write $\beta_q = 2r+1$ with $r \in \mathbb{N}_0$. After applying the preceding division step $r$ times, the integer
\begin{align*}
\frac{n}{q^{2r}} = qm
\end{align*}
would still be a sum of two squares. Applying the previous step once more would imply $q^2 \mid qm$, hence $q \mid m$, contradicting the choice of $m$. Therefore $\beta_q$ is even.
[guided]
Fix a prime $q \equiv 3 \pmod 4$. The previous step says that whenever $q$ divides a represented integer $a^2+b^2$, it divides both $a$ and $b$. This is stronger than just saying $q \mid n$: it says the representation itself contains a factor of $q$ in both entries.
Write
\begin{align*}
n = q^{\beta_q}m
\end{align*}
where $m \in \mathbb{N}$ and $q \nmid m$. If $\beta_q = 0$, the required parity statement is immediate. Now suppose $\beta_q \geq 1$. Since $q \mid n = a^2+b^2$, the obstruction from the previous step gives integers $a_1,b_1 \in \mathbb{Z}$ such that
\begin{align*}
a = qa_1,
\qquad
b = qb_1.
\end{align*}
Substituting into the representation gives
\begin{align*}
n = a^2+b^2 = q^2a_1^2+q^2b_1^2 = q^2(a_1^2+b_1^2).
\end{align*}
Thus $q^2 \mid n$, and after dividing by $q^2$ we still have a representation:
\begin{align*}
\frac{n}{q^2} = a_1^2+b_1^2.
\end{align*}
The same argument applies again to this quotient if it remains divisible by $q$. Hence the exponent of $q$ can be removed from a represented integer only two powers at a time.
If $\beta_q$ were odd, say $\beta_q = 2r+1$, then after removing $2r$ powers by this repeated argument, the integer
\begin{align*}
\frac{n}{q^{2r}} = qm
\end{align*}
would still be represented as a sum of two squares. Since $q$ divides $qm$, the previous step would force $q^2 \mid qm$. That means $q \mid m$, contradicting the definition of $m$ as the part of $n$ not divisible by $q$. Therefore $\beta_q$ must be even.
[/guided]
[/step]
[step:Prove that products of represented integers are represented]
Let $A,B \in \mathbb{N}$ be represented as sums of two squares:
\begin{align*}
A = a^2+b^2,
\qquad
B = c^2+d^2
\end{align*}
for some $a,b,c,d \in \mathbb{Z}$. Define integers
\begin{align*}
u &= ac-bd, &
v &= ad+bc.
\end{align*}
Then
\begin{align*}
u^2+v^2
&= (ac-bd)^2+(ad+bc)^2 \\
&= a^2c^2 -2abcd + b^2d^2 + a^2d^2 +2abcd + b^2c^2 \\
&= a^2(c^2+d^2)+b^2(c^2+d^2) \\
&= (a^2+b^2)(c^2+d^2) \\
&= AB.
\end{align*}
Thus the product of two positive integers represented as sums of two squares is again represented as a sum of two squares.
[guided]
To build representations of large products, we need a multiplication rule. Suppose
\begin{align*}
A = a^2+b^2,
\qquad
B = c^2+d^2
\end{align*}
with $a,b,c,d \in \mathbb{Z}$. The correct new entries are
\begin{align*}
u &= ac-bd, &
v &= ad+bc.
\end{align*}
These are integers because they are formed from $a,b,c,d$ using integer addition and multiplication. Expanding the sum of their squares gives
\begin{align*}
u^2+v^2
&= (ac-bd)^2+(ad+bc)^2 \\
&= a^2c^2 -2abcd + b^2d^2 + a^2d^2 +2abcd + b^2c^2.
\end{align*}
The mixed terms cancel exactly. Grouping the remaining terms by $a^2$ and $b^2$ gives
\begin{align*}
u^2+v^2
&= a^2(c^2+d^2)+b^2(c^2+d^2) \\
&= (a^2+b^2)(c^2+d^2) \\
&= AB.
\end{align*}
Therefore, whenever two integers have two-square representations, their product has one as well. This identity is the algebraic mechanism that lets us combine the prime-power representations in the factorisation of $n$.
[/guided]
[/step]
[step:Represent every prime-power factor allowed by the parity condition]
Assume now that every exponent $\beta_q$ with $q \equiv 3 \pmod 4$ is even.
The factor $2^e$ is represented because
\begin{align*}
2 = 1^2+1^2
\end{align*}
and repeated use of the product identity represents every power $2^e$, with $2^0=1=1^2+0^2$.
For each prime $p \equiv 1 \pmod 4$ with $\alpha_p > 0$, Fermat's prime two-square theorem (citing a result not yet in the wiki: every prime $p \equiv 1 \pmod 4$ is a sum of two squares) gives integers $r_p,s_p \in \mathbb{Z}$ such that
\begin{align*}
p = r_p^2+s_p^2.
\end{align*}
Repeated use of the product identity then represents $p^{\alpha_p}$.
For each prime $q \equiv 3 \pmod 4$, write $\beta_q = 2\gamma_q$ with $\gamma_q \in \mathbb{N}_0$. Then
\begin{align*}
q^{\beta_q} = q^{2\gamma_q} = (q^{\gamma_q})^2 + 0^2,
\end{align*}
so each such prime-power factor is represented.
[/step]
[step:Combine the represented prime powers to represent $n$]
Only finitely many exponents in the prime factorisation of $n$ are nonzero, so $n$ is a finite product of represented positive integers:
\begin{align*}
2^e,\qquad p^{\alpha_p}\text{ for }p \equiv 1 \pmod 4,\qquad q^{\beta_q}\text{ for }q \equiv 3 \pmod 4.
\end{align*}
Starting from the representation $1=1^2+0^2$ and applying the product identity finitely many times, the full product
\begin{align*}
n = 2^e \prod_{\substack{p \text{ prime} \\ p \equiv 1 \pmod 4}} p^{\alpha_p}
\prod_{\substack{q \text{ prime} \\ q \equiv 3 \pmod 4}} q^{\beta_q}
\end{align*}
is represented as $a^2+b^2$ for some $a,b \in \mathbb{Z}$. This proves the sufficiency direction, and together with the necessity direction completes the proof.
[/step]
