It's well known that a positive integer $n$ is a sum of two squares if and only if every prime of the form $4m + 3$ that divides $n$ appears with even multiplicity in the prime factorization of $n$. My question is:

For which positive integers $n$ do there exist $a, b \in \mathbf{Z}$ such that $(a, b) = 1$ and $n = a^2 + b^2$?

I have done some work on this. We can use the arithmetic of $\mathbf{Z}[i]$ to show that no prime of the form $4n + 3$ can divide such an $n$. Indeed, if $p \equiv 3 \bmod{4}$ is a prime that divides $n$, then $p|(a + bi)(a - bi)$ in $\mathbf{Z}[i]$. Because $p$ stays prime in $\mathbf{Z}[i]$, either $p|(a + bi)$ or $p|(a - bi)$, and each of these situations implies $p|a$ and $p|b$, contradicting our assumption that $(a, b) = 1$.

Furthermore, $n$ cannot be divisible by four. If it were then $a^2 + b^2 \equiv 0 \bmod{4}$, and because the only quadratic residues mod four are zero and one, we must have $a^2 \equiv b^2 \equiv 0 \bmod{4}$, meaning $a$ and $b$ are both even, which again contradicts $(a, b) = 1$.

Therefore, any integer $n$ satisfying the desired properties must be of the form $$n = 2^e p_1 \cdots p_m$$ where $e = 0, 1$ and each $p_i \equiv 1 \bmod{4}$. Some numerical exploration suggests that any number of this form can be expressed as a sum of two relatively prime squares. It suffices to prove the case $e = 0$, because if $$p_1 \cdots p_m = c^2 + d^2 \text{ where } (c, d) = 1,$$ then $$2p_1 \cdots p_m = (c + d)^2 + (c - d)^2,$$ and the coprimality of $c$ and $d$ implies $(c + d, c - d) = 1$.

Therefore, the problem is reduced to proving the following statement, which I believe to be true.

Any product of primes of the form $4n + 1$ is a sum of two relatively prime squares.

Can someone provide a hint towards a proof of this?

  • induction on the total of the exponents. Product: what is $(a+bi)(c+di)?$ – Will Jagy Nov 24 '14 at 2:20
  • 3
    This is correct, and a proof can be found in lots of number theory textbooks - for example, Niven/Zuckerman/Montgomery. – Greg Martin Nov 24 '14 at 2:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.