Integer as Sum of Two Squares

Theorem

Let $n$ be a positive integer.

Then $n$ can be expressed as the sum of two squares iff each of its prime divisors of the form $4 k + 3$ (if any) occur to an even power.

Proof

Let us extract the largest square divisor of $n$, and write:

$n = m^2 r$

where $r$ is square-free.

Necessary Condition

Suppose $r$ has no prime divisor in the form $4 k + 3$.

If $r = 1$ then $n^2 = m^2 + 0^2$ and nothing needs to be proved.

If $r > 1$ then $r$ is a product of one or more primes, each of which is either $2$ or in the form $4 k + 1$.

Now from Prime as Sum of Two Squares, each of these can be expressed as the sum of two squares.

By Product of Sums of Two Squares, the product of all these can itself be expressed as the sum of two squares.

So $r = a^2 + b^2$, say.

Then $n = m^2 \left({a^2 + b^2}\right) = \left({m a}\right)^2 + \left({m b}\right)^2$.

So $n$ can be expressed as the sum of squares.

Sufficient Condition

Now suppose that $n$ can be expressed as the sum of squares, say $n = m^2 r = a^2 + b^2$.

First, any common divisor of $a$ and $b$ may be cancelled as follows.

If $\gcd \left\{{a, b}\right\} = d$, then we can write $a = a' d, b = b' d$ where $\gcd \left\{{a', b'}\right\} = 1$ from Divide by GCD for Coprime Integers.

So:

$m^2 r = d^2 \left({a'^2 + b'^2}\right)$.

As $r$ is square-free, $d \backslash m$ and so, writing $m' = \frac m d$, we get:

$m'^2 r = a'^2 + b'^2$.

We need to show that $r$ has no prime factor of the form $4 k + 3$.

To obtain a contradiction, we suppose $p = 4 k + 3$ divides $r$.

Then:

$a'^2 + b'^2 \equiv 0 \implies a'^2 \equiv -b'^2 \pmod p$.

If $p \backslash a'$ we would have $p \backslash b'$ which contradicts $\gcd \left\{{a', b'}\right\} = 1$.

So $\gcd \left\{{a', p}\right\} = \gcd \left\{{b', p}\right\} = 1$ and we can apply Fermat's Little Theorem:

$a'^{p-1} \equiv b'^{p-1} \equiv 1 \pmod p$.

So, we put $p = 4 k + 3$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 1\)	\(\equiv\)	\(\displaystyle a'^{p-1}\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle a'^{4 k + 2}\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({a'^2}\right)^{2 k + 1}\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({-b'^2}\right)^{2 k + 1}\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({-1}\right)^{2 k + 1} \left({b'^2}\right)^{2 k + 1}\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({-1}\right) b'^{p-1}\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle -1\)	\(\displaystyle \)	\(\displaystyle \pmod p\)	\(\displaystyle \)

$-1 \equiv 1 \pmod p$ is not possible for an odd prime.

So we have obtained our contradiction.

The result follows.

$\blacksquare$