If $m$ is an odd number whose prime factors are all $\equiv 1\pmod{4}$, then $m=a^2+b^2$, where $\gcd(a,b)=1$.

Question

This is exercise 24.5.(a) from the book A Friendly Introduction To Number Theory:

If $m$ is odd and if every prime dividing $m$ is congruent to 1 modulo 4, prove that $m$ can be written as a sum of two squares $m = a^2 + b^2$ with $\gcd(a, b) = 1$.

This is what I've tried:

Let $m=p_1p_2\cdots p_r M^2$, where the $p_i$'s are distinct primes $\equiv 1\pmod{4}$. Fermat's theorem on sums of two squares tells us each $p_i$ can be written as a sum of two squares. Moreover, since a product of 2 sums of 2 squares is also a sum of 2 squares, we can express $p_1p_2\cdots p_r=a^2+b^2$. It is clear that $\gcd(a,b)=1$, since $$d\mid a,b\implies d^2\mid p_1p_2\cdots p_r,$$ and the product $p_1p_2\cdots p_r$ is squarefree. So we can express $m$ as a sum of two squares: $$m^2=(a^2+b^2)M^2=(aM)^2+(bM)^2.$$ However, $aM$ and $bM$ are clearly not relatively prime. How can one follow this proof to obtain two relatively prime numbers $A,B$ such that $m=A^2+B^2$?

Answer 1

Here's an (ugly) proof I came up with:

Let $m=p_1p_2\cdots p_r$, where the primes $p_i$ are $\equiv 1\pmod{4}$ and not necessarily distinct. We prove that $m=A^2+B^2$, where $\gcd(A,B)=1$, by induction on $r$, the number of prime factors of $m$:

• $\mathbf{r=1}$. In that case, $m$ is a prime congruent to $1\pmod{4}$, so $m=A^2+B^2$. Moreover, $\gcd(A,B)=1$, since if a prime $p$ divided simultaneously $A$ and $B$, then $p^2\mid m$, a contradiction.
• $\mathbf{r>1}$. By induction hypothesis, we can write $$m=p_1(p_2\cdots p_r)=(\underbrace{a^2+b^2}_{p_1})(\underbrace{c^2+d^2}_{p_2\cdots p_r}),$$ where $\gcd(a,b)=1$ and $\gcd(c,d)=1$. Furthermore, this product can be rewritten as a sum of two squares in two different ways: $$(a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(bc\mp ad)^2.$$ We prove that, either $x:=ac+ bd$ and $y:=bc- ad$ are relatively prime, or $u:=ac-bd$ and $v:=bc+ad$ are relatively prime. In order to arrive to a contradiction, suppose the contrary: take a prime $p$ such that $p\mid x,y$, and another prime $q$ such that $q\mid u,v$. Notice that $$\begin{cases} p\mid ax+by=c(a^2+b^2)\\[1ex] p\mid bx-ay=d(a^2+b^2) \end{cases}\stackrel{\gcd(c,d)=1}{\implies}p\mid a^2+b^2 \implies p=p_1.$$ Analogously,

$$\begin{cases} q\mid c u +d v=a(c^2+d^2)\\[1ex] q\mid c v - du=b(c^2+d^2) \end{cases}\stackrel{\gcd(a,b)=1}{\implies} q\mid c^2+d^2.$$ Moreover, $q\mid xv-yu=2pcd$. It is easy to see that this implies $p=q$. But then, $p\mid x+u=2ac$, which is impossible.