Prove Corollary (8.8).
Let's remind ourselves of Corollary (8.8):
Let $n = p_1 \times p_2 \times \ldots \times p_r \times 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$.
The two directions of this Corollary are each Theorems (8.5) and (8.7), noting that the negation of $p_j \equiv 3 \pmod 4$ is $p_j =2 \lor p_j \equiv 1 \pmod 4$.
Prove Theorem (8.7).
Let's remind ourselves of Converse of Sum of Two Squares Theorem (8.7).
Let $m = p_1 \times p_2 \times \ldots \times p_r × N^2$ where $p$’s are distinct primes. If $m$ can be expressed as sum of two squares then none of these primes $p_j$ satisfies $p_j \equiv 3 \pmod 4$ for $j= 1, \ldots , r$.
Suppose for the purpose of contradiction that there exists a prime $p$ amongst the $p_j$ such that $p\equiv3 \pmod 4$.
We are assuming $m$ can be expressed as a sum of two squares, so for some natural numbers $a,b$ we have
$$ m= a^2 +b^2 = p_1 \times p_2 \times \ldots \times p_r \times N^2 $$
This means $p \mid a^2 + b^2$. That is
$$ a^2 \equiv -b^2 \pmod p $$
Let's now consider the quadratic residue $-b^2 \pmod p$
$$ (\frac{-b^2}{p}) = (\frac{-1}{p}) \times (\frac{b^2}{p}) = (\frac{-1}{p}) \times (1) = (\frac{-1}{p}) $$
For $ a^2 \equiv -b^2 \pmod p $ to have a solution, this requires $p \equiv 1 \pmod 4$ by Proposition (7.11).
This contradicts $p \equiv 3 \pmod 4$, and so proves the Theorem.
Prove the following:
If $n$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r−1}$.
We will prove this by induction.
Let $S(r)$ be the statement:
If $n$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r−1}$.
We need to prove the base case $S(1)$ and the inductive step $S(r) \implies S(r+1)$.
Base Case $S(1)$
The base case is
If $n$ is the product of 1 distinct prime $p$ which satisfies $p \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is 1.
In the previous exercise we showed that a prime $p_j$ satisfying $p_j \equiv 1 \pmod 4$ can be written uniquely as a sum of squaresm, which proves the base case.
Induction Step $S(r) \implies S(r+1)$
The statement $S(r+1)$ is
If $n$ is the product of $r+1$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r}$.
We assume $S(r)$ as the induction hypothesis
If $m$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $m$ can be expressed as a sum of two squares is $2^{r−1}$.
Here $n = m \times p$ where $p$ is distinct from any prime in $m$ and satisfies $p \equiv 1 \pmod p$.
Since $p$ can be uniquely written as a sum of squares, $p=a^2 +b^2$, we have
$$ n = m \times (a^2 + b^2) $$
But $m$ can also be written as a sum of squares, $m = c^2+d^2$, we have by the two conversion identities
$$ n = (c^2 + d^2) \times (a^2 + b^2) = (ca-db)^2 + (cb+da)^2 $$
$$ n = (c^2 + d^2) \times (a^2 + b^2) = (ca+db)^2 + (cb-da)^2 $$
We now show the sums of squares are distinct:
By assumption $m$ can be written as a sum of squares in $2^{r-1}$ ways, and since $p$ can be written in two ways, this means $n$ can be written as a sum of squares in $2^{r-1}\times 2 = 2^r$ was, proving the induction step.
By induction we have shown that if $n$ is the product of $r$ distinct primes $p_j$ which satisfy $p_j \equiv 1 \pmod 4$ then the number of different ways $n$ can be expressed as a sum of two squares is $2^{r−1}$.
Note: there is an unproven assumption here, and in the author's solution, that $(c^2 + d^2) \times (a^2 + b^2)$ can be written in two different forms, $(ca-db)^2 + (cb+da)^2 $ and $(ca+db)^2 + (cb-da)^2$, and no more.
(i) Prove the following: A prime $p$ satisfying $p \equiv 1 \pmod 4$ can be written uniquely as the sum of two squares.
(ii) Prove Theorem (8.4).
(i) We know from Theorem (8.3) that a prime $p$ satisfying $p \equiv 1 \pmod 4$ can be written as the sum of two squares.
For the purpose of contradiction, let's assume $p$ can be written as a sum of two squares in two different ways.
$$ p = a^2 + b^2 = c^2 + d^2 $$
where $a, b, c, d$ are distinct, and all greater than 0, otherwise $p$ would not be prime.
The Conversion Identity (8.1), and question 12, gives us
$$ p^2 = (a^2 + b^2) (c^2 + d^2) = (ac− bd)^2 + (ad + bc)^2 = (ac+bd)^2 + (ad - bc)^2 $$
Now $p - a^2 = b^2$ and $p-c^2=d^2$, and so
$$ (p-a^2)d^2 = b^2d^2 = (p-c^2)b^2 $$
which gives us
$$ p(d^2-b^2) = a^2d^2 -b^2c^2 = (ad-bc)(ad+bc) \tag{i}$$
This means
$$ p \mid (ad-bc) \quad \lor \quad p \mid (ad+bc) $$
and so
$$ p^2 \mid (ad-bc)^2 \quad \lor \quad p^2 \mid (ad+bc)^2 $$
or for some integers $m,n$
$$ p^2m = (ad-bc)^2 \quad \lor \quad p^2 n = (ad+bc)^2 $$
Let's consider each case in turn.
Case $ p^2m = (ad-bc)^2$
From the conversion identities,
$$ p^2(1-m) = (ac+bd)^2 $$
Because $a,b,c,d$ are all greater than 0, this means $m=0$. And so $(ad-bc)^2=0$, that is, $ad-bc = 0$. Using this in (i) gives us $d^2-b^2 = 0$, that is $d=b$. Using $a^2+b^2 = c^2 + d^2$ with $d=b$ gives $a=c$. So we have
$$ a=c, \quad b=d $$
Case $ p^2 n = (ad+bc)^2$
From the conversion identitues,
$$ p^2(1-n) = (ac− bd)^2 $$
Here $n$ could be 1 or 0. But $n\ne0$, because that would mean $p^2 = (ac− bd)^2$ and from the conversion identities, that would mean $(ad + bc)^2=0$, a contradiction. And so $n=1$, which means $(ac-bd)^2=0$, that is $ac-bd=0$.
From $p-a^2=b^2$ and $p-d^2=c^2$, we have $(p-a^2)c^2=b^2c^2=(p-d^2)b^2$, which gives us
$$ p(c^2-b^2) = a^2c^2 - d^2b^2 = (ac-bd)(ac+bd) $$
Using $ac-bd=0$ with this gives $c^2-b^2=0$, that is $c=b$, which also gives us $a=d$. So we have
$$ a=d \quad b=c $$
Both cases lead to non-distinct sum of squares, and so we have shown that a prime $p$ satisfying $p \equiv 1 \pmod 4$ can be written uniquely as the sum of two squares.
(ii) Let's remind ourselves of Theorem (8.4):
An odd prime $p$ can be written as sum of two squares uniquely if and only if $p \equiv 1 \pmod 4$.
We have proved one direction in part (i) above. We only need to show that if a prime can be written uniquely as a sum of two squares then $p \equiv 1 \pmod 4$.
Let's write $p=a^2+b^2$ for some positive integers $a,b$. We know from Exercise (1.2).2 that the square of an integer is congruent to 0 or 1 modulo 4.
This means $p$ is congruent to 0, 1 or 2 modulo 4. But since $p$ is an odd prime, then $p$ cannot be congruent to 0 or 2 modulo 4, leaving only
$$ p \equiv 1 \pmod 4 $$
This concludes the proof.
Disprove the following statements:
(a) If $m$ is a sum of two squares and $m \mid n$ then $n$ is also a sum of two squares.
(b) If both $m$ and $n$ can be expressed as sum of two squares then $m + n$ can also be written as sum of two squares.
(c) Assume all three positive distinct integers $n_1$, $n_2$, and $n_3$ cannot be expressed as a sum of two squares. Therefore, $n_1 + n_2 + n_3$ cannot be expressed as a sum of two squares.
We will disprove the statements with counter-examples.
(a) Let $m=5=2^2 + 1^2$, and $n=15$.
We have $m \mid n$. But $15=3 \times 5$ and $3 \equiv 3 \pmod 4$, and so by Corollary (8.8) we can't write $n$ as the sum of two squares.
(b) Let $m=2=1^1+1^2$ and $n=5=2^2+1^2$.
Here $m+n=7$, a prime congruent to 3 modulo 4, and so by Corollary (8.8) we can't write $m+n$ as the sum of two squares.
(c) Let $n_1=3, n_2=7, n_3=15$.
Here $n_1-3$ and $n_2=7$ are primes congruent to 3 modulo 4 and so can't be written as a sum of two squares by Theorem (8.5).
Similarly $n_3=15=3 \times 5$ has a single prime factor 3 congruent to 3 modulo 4, and so can't be written as a sum of two squares by Theorem (8.5).
The sum $n_1+n_2+n_3=25=5^2 + 0^2$, and so can be written as the sum of two squares.
Let $n = 2 \times p^e × q^k$ where $p \equiv 3 \pmod 4$, $e$ is even, $q \equiv 1 \pmod 4$, and $k$ is any natural number.
Show that $n$ can be expressed as a sum of two squares.
We will use Sum of Two Squares Theorem (8.5).
Let $m$ be a positive integer given by $m = p_1 \times p_2 \times \ldots × p_r × N^2$ where the $p$’s are distinct primes. Then $m$ can be expressed as a sum of two squares, provided every prime $p_j$ satisfies $p_j = 2$ or $p_j \equiv 1 \pmod 4$ for $j= 1, \ldots , r$.
Because $e$ is even, we can write it as $e=2a$, for some natural number $a$.
There are two cases for $k$, even and odd. Let's consider both in turn.
Case $k$ even
If $k$ is even, we can write it as $k=2b$ for some natural number $b$. And so
$$ n = 2 \times p^e \times q^k = 2 \times (p^a)^2 \times (q^b)^2 = 2 \times (p^aq^b)^2 $$
By the Sum of Two Squares Theorem (8.5), $n$ can be written as a sum of two squares.
Case $k$ odd
If $k$ is odd, we can write it as $k=2b+1$ for some natural number $b$. And so
$$ n = 2 \times p^e \times q^k = 2 \times (p^a)^2 \times (q^b)^2 \times q= 2 \times (p^aq^b)^2 \times q $$
Since $q \equiv 1 \pmod 4$, by the Sum of Two Squares Theorem (8.5), $n$ can be written as a sum of two squares.
(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.
Prove the following:
If $n = p \times q$ where $p \equiv q \equiv 1 \pmod 4$ then we can write $n$ as a sum of two squares.
We assume $p, q$ are primes.
Since $p \equiv q \equiv 1 \pmod 4$, by Theorem (8.3), they can be written as a sum of two squares. So let's write $p=a^2 + b^2$ and $q=c^2 + d^2$.
By the Conversion Identity (8.1),
$$ n = p \times q = (a^2+b^2)(c^2 + d^2) = (ac-bd)^2 + (ad+bc)^2$$
And so $n$ can be written as the sum of two primes.
Find all four different representations of $1105= 5 × 13 × 17$ as a sum of two squares.
We will use the Conversion Identity (8.1):
$$ (a^2 + b^2) (c^2 + d^2) = (ac− bd)^2 + (ad + bc)^2 $$
We first note that each prime factor 5, 13, and 17 are congruent to 1 modulo 4, so 1105 can be written as the sum of two squares.
We also note that
$ 5 = 2^2 + 1^2 $
$ 13 = 3^2 + 2^2 $
$ 17 = 4^2 + 1^2 $
Since there are 3 factors, the conversion identity becomes:
$$ \begin{align} (a^2 + b^2) (c^2 + d^2)(e^2 + f^2) & = ((ac− bd)^2 + (ad + bc)^2)(e^2 + f^2) \\ \\ & = (A^2 +B^2)(e^2 + f^2) \\ \\ & = (Ae - Bf)^2 + (Af+Be)^2 \end{align} $$
where $A = (ac− bd)$ and $B = (ad + bc)$.
This could be four different sum of squares by
The following table shows these calculations.
| product | a | b | c | d | A = (ac − bd) | B = (ad + bc) | e | f | (Ae-Bf) | (Af+Be) | (Ae-Bf)^2+(Af+Be)^2 |
| 5 x 13 | 2 | 1 | 3 | 2 | 4 | 7 | 4 | 1 | 9 | 32 | 1105 |
| 5 x 13 | 1 | 2 | 2 | 3 | 7 | -4 | 1 | 4 | 23 | 24 | 1105 |
| 5 X 17 | 2 | 1 | 4 | 1 | 7 | 6 | 3 | 2 | 9 | 32 | 1105 |
| 5 X 17 | 1 | 2 | 1 | 4 | 6 | -7 | 2 | 3 | 33 | 4 | 1105 |
| 13 x 17 | 3 | 2 | 4 | 1 | 10 | 11 | 2 | 1 | 9 | 32 | 1105 |
| 13 x 17 | 2 | 3 | 1 | 4 | 11 | -10 | 1 | 2 | 31 | 12 | 1105 |
We can read off the four distinct combinations:
$$ \begin{align} 1105 & = 32^2 + 9^2 \\ \\ 1105 & = 24^2 + 23^2 \\ \\ 1105 & = 33^2 + 4^2 \\ \\ 1005 & = 31^2 + 12^2 \end{align} $$