(a) Explain why 6 cannot be expressed as a sum of two squares.
(b) Show that if $n \equiv 3$ or $6 \pmod 9$ then $n$ cannot be expressed as a sum of two squares.
(c) Show that if
$$ n \equiv 6, 12, 24, 30 \pmod {36} $$
then $n$ cannot be expressed as a sum of two squares.
(d) Explain why we cannot say
$$ n \equiv 18 \pmod {36}$$
can be written as a sum of two squares.
(a) Let's remind ourselves of Corollary (8.8):
Let $n = p_1 \times p_2 \times \ldots \times p_r × N^2$ where $p$’s are distinct primes. Then $n$ cannot be expressed as a sum of two squares if and only if it has a prime factor $p_j \equiv 3 \pmod 4$ for any $j= 1, \ldots , r$.
We note that $ 6 = 2 \times 3 $, and $3 \equiv 3 \pmod 4$.
By Corollary (8.8) 6 cannot be expressed as a sum of two squares, because one of primes in its prime factorisation is congruent to 3 modulo 4.
(b) We have two cases to consider, $n \equiv 3 \pmod 9$ and $n \equiv 6 \pmod 9$.
If $n \equiv 3 \pmod 9$, we can write $n=9k+3 = 3(3k+1)$ for some integer $k$. And so 3 is single prime factor of $n$, because 3 does not divide $(3k+1)$. By Corollary (8.8), this means $n$ cannot be expressed as a sum of squares.
If $n \equiv 6 \pmod 9$, we can write $n=9k+6 = 3(3k+2)$ for some integer $k$. And so 3 is single prime factor of $n$, because 3 does not divide $(3k+1)$. By Corollary (8.8), this means $n$ cannot be expressed as a sum of squares.
(c) If $ n \equiv 6, 12, 24, 30 \pmod {36} $ then for some integer $k$
$$ n = 36k + 6,12,24,30 = 3(12k + 2,4,8,10) $$
This tells 3 is a factor of $n$, and is only one factor 3, because 3 does not divide $(12k+2,4,8,10)$. By Corollary (8.8) this means $n$ cannot be expressed as a sum of squares.
(d) If $n \equiv 18 \pmod {36}$ then for some integer $k$
$$ n = 36k + 18 = 2 \times 3^2 \times (2k+1) $$
It is possible for $(2k+1)$ to be congruent to 3 modulo 4 whilst also being a prime distinct from 3. For example $k=3$ gives $(2k+1)=7 \equiv 3 \pmod 4$.
And so by Corollary (8.8) $n$ can not always be written as the sum of two squares.