Let $m$ be an odd positive integer. Show that $m$ can be
written as a sum of two squares $m = a^2 + b^2$ with $\gcd(a,b) = 1$ if and only if every
prime factor of $m$ is congruent to $1 (\text{mod}~4)$.
$\mathbf{My~Attempts:}$
Notice that if $m$ is an odd prime, then the statement holds by Fermat's theorem on sums of two squares.
So, let $m$ be the composite odd positive integer.
First prove if every prime factor of $m$ is congruent to $1~(\text{mod}\ 4)$ then $m = a^2 + b^2$ with $\gcd(a,b) = 1$.
Assume that every prime factor of $m$ is congruent to $1~(\text{mod}\ 4)$
Let $m = p_1 p_2 \cdots p_n$ be the prime factorization of $m$ and each $p_i$ are odd.
Then, by assumption, each $p_i \equiv 1 ~(\text{mod}~4)$ which by Fermat's theorem on sums of two squares, $p_i = a_i^2 + b_i^2$ for some $a_i, b_i \in \mathbb{N}$.
So, $m = (a_1^2 + b_1^2)(a_2^2 + b_2^2) \cdots (a_n^2 + b_n^2) = [(a_1 a_2 + b_1 b_2)^2 + (b_1 a_2 – a_1 b_2)^2](a_3^2 + b_3^2) \cdots (a_n^2 + b_n^2)$.
Let $x_1 = (a_1 a_2 + b_1 b_2)$ and $y_1 = (b_1 a_2 – a_1 b_2)$.
Then, we have $m = (x_1^2 + y_1^2)(a_3^2 + b_3^2) \cdots (a_n^2 + b_n^2)$.
Now repeat this process $n-2$ times and let each $x_i = (x_{i-1} a_{i+1} + y_{i-1} b_{i+1})$ and let each $y_i = (y_{i-1} a_{i+1} – x_{i-1} b_{i+1})$.
Then, we will have $m = (x_{n-1}^2 + y_{n-1}^2)$ where $x_{n-1} = (x_{n-2} a_n + y_{n-2} b_n)$ and $y_{n-1} = (y_{n-2} a_n – x_{n-2} b_n)$.
Where $x_{n-1}$ and $y_{n-1}$ are both positive integers.
Let $a = x_{n-1}$ and $b = y_{n-1}$.
So, we proved that $m$ can be written as a sum of two squares $m = a^2 + b^2$.
$\mathbf{Problems:}$
Now I stuck on how to prove that $\gcd(a,b) = 1$ in this case !!
Also, I don't know how to prove the inverse of the statement where if $m = a^2 + b^2$ with $\gcd(a,b) = 1$ then every prime factor of $m$ is congruent to $1~(\text{mod}~4)$ !
Best Answer
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}$.