The prime power decomposition of sum of two squares 
Show that if an integer is a sum of two squares: $n=x^2+y^2$, then in the prime power decomposition of $n$, all primes $p = 3 \pmod{4}$ appear with even exponents :
For $p = 3 \pmod{4}$, if $p^k \mid n$ but $p^{k+1}$ doesn't then $k$ is even.

So I saw this - Prime-power decomposition of a square
But it's quite different...
Any ideas?
 A: Let $p \equiv 3 \pmod{4}$, with $p$ prime. You should know 
$$\tag{noroot}
\text{there is no $w$ such that $w^{2} \equiv -1 \pmod{p}$.}
$$ This is simply because if $p = 3 + 4 a$, the group of invertible elements modulo $p$ has order $$p - 1 = 2 (1 + 2 a) = 2 \cdot \text{odd number},$$ for some $a$, so it cannot have an element of order $4$ as $w$ would be.
Suppose by way of contradiction $$p^{2 k+1} \mid x^{2} + y^{2}, \quad\text{but}\quad p^{2 k+2} \nmid x^{2} + y^{2}.$$ We argue by induction on $k \ge 0$.
If $p \nmid x$, then $x$ has an inverse $z$ modulo $p$. Multiply $0 \equiv x^{2} + y^{2} \pmod{p}$ by $z$ to get
$$
-1 \equiv (z y)^{2} \pmod{p},
$$
a contradiction to (noroot).
Thus $p \mid x$, so that $p \mid y$ as well. If $k = 0$, this is a contradiction, because then $p^{2} \mid x^{2}, y^{2}$, so that $p^{2} \mid n$.
If $k > 0$, you get that
$$p^{2 k-1} \mid \left(\frac{x}{p}\right)^{2} + \left(\frac{y}{p}\right)^{2},$$ 
but 
$$p^{2 k} \nmid \left(\frac{x}{p}\right)^{2} + \left(\frac{y}{p}\right)^{2}.
$$ 
Induction now applies.

There is at least another proof, which involves Gaussian integers $G$. It is pretty easy to show that such a $p$ remains prime in $G$. Then if $p \mid x^{2} + y^{2} = (x + i y) (x - i y)$, it has to divide one of the factors, and thus both, as they are complex conjugates and $p$ is real. Now if $p^{e}$ is the largest power of $p$ dividing $x - i y$, then $p^{e}$ is also the largest power of $p$ dividing $x + i y$, so that $p^{2 e}$ is the largest power of $p$ dividing $x^{2} + y^{2}$.
A: As pointed out by @Piquito, your problem is classically treated in any textbook on ANT. If you need to work it out, there is a concise answer using the Gaussian integers. The starting point is to decompose a rational prime $p$ in the ring   $A=\mathbf Z[i]$, which is a UFD. Result: $p$ splits in $A$ (i.e. $p$ is, up to $\pm 1, \pm i$ , a poduct of two distinct - necessarily complex conjugate - irreducible elements) iff $p$ is a sum of two squares, iff $p \equiv 1$ mod $4$. Consequence: given an integer $n$ written as a product of powers of distinct primes $p^{v_p (n)}$, $n$ is a sum of two squares iff, for all $p \equiv 3$ mod $4, {v_p (n)}$ is even.  
A: That's not true since there is no $x$ such that $x^2$ $=$ $-1$ $\pmod p$ if $p$ $=$ $3$ $\pmod 4$ or $d$ $|$ $p$ and $d$ $=$ $3$ $\pmod 4$. Factoring $x^2+y^2$ with real, or irrational numbers is impossible, you can factor it with imaginary numbers: $x^2+y^2$ $=$ $(x+iy)(x-iy)$, and $i^2$ $=$ $-1$.
