It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian integers that lets you prove this quickly. Can anyone explain it?
[Math] Fermat’s Two Square Theorem: How to prove that an odd prime is the sum of two squares iff it is congruent to 1 mod 4
elementary-number-theoryprime numbers
Related Solutions
A postive integer $n$ is representable as the sum of two squares, $n=x^2+y^2$ if and only if every prime divisor $p\equiv 3$ mod $4$ of $n$ occurs with even exponent. This is good enough to solve your questions.
a) $n=363=3\cdot 11^2$ is not the sum of two squares, since $3$ is a prime divisor $p\equiv 3$ mod $4$ occuring not with even multiplicity.
b) $n=700=2^2\cdot 5^2\cdot 7$ is not the sum of two squares. Take $p=7$.
c) $n=34300=2^2\cdot 5^2\cdot 7^3$ is not the sum of two squares. Take $p=7$.
d) $n=325=5^2\cdot 13$ is a sum of two squares, because every prime divisor $p\equiv 3$ mod $4$ occurs with even multiplicity - because $0$ is even. Of course, it is straightforward to see that, say, $325=10^2+15^2$.
Here's a somewhat different approach. First, similar to what you did, the "if" part means each prime factor of $m$ is congruent to $1 \pmod{4}$. As shown in the answer to Sum of two squares and prime factorizations, Fermat's theorem on the sum of squares states each prime factor $p_i$ of $m$ can be written as the sum of squares. Also, for any $c, d, e, f \in \mathbb{R}$,
$$(c^2 + d^2)(e^2 + f^2) = (ce \pm df)^2 + (cf \mp de)^2 \tag{1}\label{eq1A}$$
shows whenever $2$ numbers can be written as a sum of squares, their product can be as well, in $2$ different ways. Using \eqref{eq1A} repeatedly with the previous result (starting at $1$) and for each $p_i \mid m$ means the final product, i.e., $m$, can be written as a sum of squares.
Regarding proving you can choose an $a$ and $b$ where $\gcd(a, b)$, the answer to Any product of primes in the form of 4n+1 is the sum of 2 relatively prime squares shows this, paraphrased below.
As shown in \eqref{eq1A}, the product of the $2$ sums of squares can be expressed in $2$ ways. Have $c^2 + d^2$, with $\gcd(c, d) = 1$, be a product of $1$ or more primes of the form $4n + 1$, and $e^2 + f^2$ be a prime of that form to be multiplied. Consider if the first form in \eqref{eq1A}, i.e., $(ce + df)^2 + (cf - de)^2$, is not valid, i.e., there's a prime $q$ which divides each term. This means
$$q \mid (ce + df)e + (cf - de)f = c(e^2 + f^2) \tag{2}\label{eq2A}$$
$$q \mid (ce + df)f - (cf - de)e = d(e^2 + f^2) \tag{3}\label{eq3A}$$
Since $q$ doesn't divide $c$ and $d$, then $q \mid e^2 + f^2 \implies q = e^2 + f^2$. If both solution types in \eqref{eq1A} are not valid, then $e^2 + f^2$ divides $ce - df$ as well as $ce + df$, and hence divides $2ce$ and $2df$. Since $e^2 + f^2$ doesn't divide $2e$ or $2f$, it must divide both $c$ and $d$, contrary to the hypothesis, meaning at least one of the $2$ forms must be valid. Thus, use the valid form, and repeat this procedure for each prime that is multiplied, to eventually get $m$.
For the "only if" part, similar to the answer to If $a \in \Bbb Z$ is the sum of two squares then $a$ can't be written in which of the following forms?, suppose there's a prime $p \equiv 3 \pmod{4}$ with $p \mid m$. If $p \mid a$, then $p \mid b$, and vice versa, but since $\gcd(a, b) = 1$, then $p$ can't divide either $a$ or $b$. Thus, $a$ has a multiplicative inverse, call it $a'$, modulo $p$. Let $r = \frac{p-1}{2}$ and note $r$ is odd. Also using Fermat's little theorem, this gives (note the argument below is basically equivalent to showing $-1$ is not a quadratic residue modulo $p$ if $p \equiv 3 \pmod{4}$)
$$\begin{equation}\begin{aligned} a^2 + b^2 & \equiv 0 \pmod{p} \\ a^2(a')^2 + b^2(a')^2 & \equiv 0 \pmod{p} \\ 1 + (ba')^2 & \equiv 0 \pmod{p} \\ (ba')^2 & \equiv -1 \pmod{p} \\ \left((ba')^2\right)^{r} & \equiv (-1)^r \pmod{p} \\ (ba')^{p-1} & \equiv -1 \pmod{p} \\ 1 & \equiv -1 \pmod{p} \end{aligned}\end{equation}\tag{4}\label{eq4A}$$
This, of course, is not possible, meaning the original assumption must be false. This confirms all prime factors of $m$ must be congruent to $1 \pmod{4}$.
Best Answer
Let $p$ be a prime congruent to 1 mod 4. Then to write $p = x^2 + y^2$ for $x,y$ integers is the same as writing $p = (x+iy)(x-iy) = N(x+iy)$ for $N$ the norm.
It is well-known that the ring of Gaussian integers $\mathbb{Z}[i]$ is a principal ideal domain, even a euclidean domain. Now I claim that $p$ is not prime in $\mathbb{Z}[i]$. To determine how a prime $p$ of $\mathbb{Z}$ splits in $\mathbb{Z}[i]$ is equivalent to determining how the polynomial $X^2+1$ splits modulo $p$.
First off, $-1$ is a quadratic residue modulo $p$ because $p \equiv 1 \mod 4$. Consequently, there is $t \in \mathbb{Z}$ with $t^2 \equiv -1 \mod p$, so $X^2+1$ splits modulo $p$, and $p$ does not remain prime in $\mathbb{Z}[i]$. (Another way of seeing this is to note that if $p$ remained prime, then we'd have $p \mid (t+i)(t-i)$, which means that $p \mid t+i$ or $t \mid t-i$.)
Anyway, as a result there is a non-unit $x+iy$ of $\mathbb{Z}[i]$ that properly divides $p$. This means that the norms properly divide as well. In particular, $N(x+iy) = x^2+y^2$ properly divides $p^2$, so is $p$ or $1$. It cannot be the latter since otherwise $x+iy$ would be a unit. So $x^2+y^2 = p$.