NTIC All the Squares Fit to be Summed

Section 13.5 All the Squares Fit to be Summed

There is one loose end. What are all the numbers we can represent as a sum of squares?

For instance, why are some composite numbers of the form

4 k + 1

not writeable as the sum of two squares? Also, many even numbers are representable – how do we tell which even numbers are writeable? We conclude our discussion by proving the full statement, after a couple of preliminary lemmas.

🔗

Lemma 13.5.1.

If $N$ has only primes of the form $4 k + 1$ and $2$ as factors, it is writeable as a sum of two squares.

🔗

Proof.

Each of those primes is representable, so we can use Fact 13.1.9 to write all intermediate products as a sum of squares. Hence all such products are representable.

🔗

Example 13.5.2.

Consider this:

442 = 2 \cdot 13 \cdot 17 = (1^{2} + 1^{2}) (3^{2} + 2^{2}) \cdot 17

= [{(1 \cdot 3 - 1 \cdot 2)}^{2} + {(1 \cdot 2 + 1 \cdot 3)}^{2}] (4^{2} + 1^{2})

= (1^{2} + 5^{2}) (4^{2} + 1^{2}) = {(1 \cdot 4 - 5 \cdot 1)}^{2} + {(1 \cdot 1 + 5 \cdot 4)}^{2} = 1^{2} + 21^{2} .

🔗

Lemma 13.5.3.

If the powers of prime factors of $N$ of the form $4 k + 3$ are only even powers, then $N$ is writeable as a sum of two squares.

🔗

Proof.

First, $p^2$ (even if $p$ is not prime) is trivially always representable, since $p^2=p^2+0^2\text{.}$ Now, rather than using Fact 13.1.9, let $P$ be the product of all prime factors of the form $4k+3\text{,}$ which is necessarily a perfect square $P=Q^2\text{,}$ given that all the powers are even. We can simply multiply this by $N/Q^2=a^2+b^2\text{,}$ which is possible by Lemma 13.5.1 since $Q^2$ removes all primes of the form $4k+3$ in the prime factorization. This yields $(aQ)^2+(bQ)^2\text{.}$

🔗

Example 13.5.4.

Consider this:

35802 = 442 \cdot 3^{4} = (1^{2} + 21^{2}) 3^{2} \cdot 3^{2}

= 1^{2} \cdot 3^{2} \cdot 3^{2} + 21^{2} \cdot 3^{2} \cdot 3^{2} = 9^{2} + 189^{2}

🔗

Theorem 13.5.5.

$N$ can be written as a sum of two perfect squares precisely if it has only even powers (including zeroth powers) of any primes of the form $4 k + 3 .$

🔗

Proof.

From 13.5.1 and 13.5.3, the only case left to consider if $N$ has a prime of the form $p=4k+3\text{,}$ but to an odd power. This seemed to be the bottleneck in our exploration.

By way of contradiction, suppose that it is possible to write

\begin{equation*} N=a^2+b^2\text{.} \end{equation*}

First, divide this equation by any factors of $p$ common to $N\text{,}$ $a\text{,}$ and $b$ to get

\begin{equation*} M=c^2+d^2 \end{equation*}

The power of $p$ we divided by (so that $N=Mp^\ell$) must be an even power, since each term on the right-hand side is a perfect square and can only contribute even powers of primes by the Fundamental Theorem of Arithmetic.

Since $N$ had an odd power of $p\text{,}$ we know $M$ still has an odd power of $p$ dividing it, yet $p\nmid c,d\text{.}$

Take everything modulo $p$ to get the congruence

\begin{equation*} 0\equiv c^2+d^2\text{ (mod }p)\text{.} \end{equation*}

Since $p \nmid c\text{,}$ we can multiply this congruence by $\left(c^{-1}\right)^2$ to get

\begin{equation*} 0\equiv 1+\left(c^{-1}\right)^2d^2\Rightarrow -1\equiv \left(c^{-1}d\right)^2\text{ (mod }p) \end{equation*}

This is a contradiction, as by Fact 13.3.2 there is no square root of $-1$ modulo $p$ for $p=4k+3\text{,}$ finishing the proof!

🔗

Example 13.5.6.

This theorem fully explains why $21 = 7 \cdot 3$ and the others mentioned in Fact 13.1.2 cannot be written as a sum of squares.

🔗

If the whole theorem still seems too neat and dried, it can be instructive to get insight by plugging in different

n

below. When do you get an error, when not?

xxxxxxxxxx
 
n=20
print(factor(n))
print(two_squares(n))

🔗

(As a bonus, can you turn this into an interactive cell? See Sage note 12.6.8.)