# Question on proveing the extended Fermat's theorem on sums of two squares

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)$$ !

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{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}\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}$$.