Exercise (8.3).15

Prove Theorem (8.21).

Let's remind ourselves of Theorem (8.21). 

Let $r = a + b\sqrt{N}$ produce the least positive solution of Pell’s equation $x^2 − Ny^2 = 1$.

Then this equation has all its positive integer solutions produced by $r^n = (a + b\sqrt{N})^n$ where $n$ is a natural number.

We are given that $r=a+b\sqrt{N}$ is the least positive solution of $x^2 - Ny^2=1$. We need to prove two things:

• Step 1: That $r^n$ produces solutions of Pell's equation.
• Step 2: All solutions are produced by $r^n$. That is, there are no solutions not produced by $r^n$.

Step 1

We have already proved Proposition (8.19) in Exercise (8.3).11 that $s^n$ produces solutions of Pell's equation if $s$ does, where $n$ is a natural number. Note that $s$ in Proposition (8.19) does not need to be the least positive solution.

Step 2

For the purpose of contradiction let's assume $q=c + d\sqrt{N}$ produces a positive solution to $x^2-Ny^2=1$, but that $r^n \ne c+d\sqrt{N}$ for any natural $n$, where $r$ is the least positive solution.

We note that $q$ is not less than or equal to $r^1$ because $r$ is the least positive solution. 

This means there exists a natural number $x$ such that

$$ r^x < q < r^{x+1} $$

Dividing by the positive number $r^x$ gives

$$ 1 < \frac{q}{r^x} < r $$

By Proposition (8.17), since $r$ is a solution, so is $r^{-1}$. Further more, by Proposition (8.19), if $r^{-1}$ is a solution, so is $(r^{-1})^x = r^{-x}$. By Proposition (8.18) the product of two solutions is also a solution, that is $q \times r^{-x} = \frac{q}{r^x}$ is a solution.

This means $ 1 < \frac{q}{r^x} < r $ is contradiction because $r$ is the least positive solution, and the positive solution $\frac{q}{r^x}$ can't be less than $r$.

And so the assumption that there exists a solution that is not a natural number power of the least positive solution is false. That is, all positive solutions are natural number powers of the least positive solution.

Exercise (8.3).14

Prove that all the positive solutions of $x^2 − 6y^2 = 1$ are produced by $r^n = (5 + 2\sqrt{6})^n$ where $n$ is a natural number.

We first find the least positive solution of $x^2 -6y^2=1$.

$y=1$ does not give an integer solution, but $y=2$ gives $x=5$. This is produced by $r=(5+2\sqrt{6})$.

By Theorem (8.21), all positive integer solutions are given by natural number powers of the least positive solution, that is,

$$ (5+2\sqrt{6})^n $$

where $n$ is a natural number.

Exercise (8.3).13

Prove Proposition (8.20).

Let's remind ourselves of Proposition (8.20). 

Let $r = a + b\sqrt{N}$ and $s = c + d\sqrt{N}$ both produce positive solutions of Pell’s equation $x^2− Ny^2 = 1$. Then $r < s \iff a < c$.

We first note that $a,b,c,d$ are all greater than or equal to 1. And since $r$ and $s$ both produce solutions of $x^2-Ny^2=1$ we have

$$  a^2 - N b^2 = 1 =  c^2 - N d^2 \tag{i} $$

We proceed as follows

$$ \begin{align} r &  < s \\ \\ a + b \sqrt{N} & < c + d \sqrt{N} \\ \\ a + \sqrt{a^2-1} & < c + \sqrt{c^2-1} \tag{using (i)} \\ \\ a & < c \end{align} $$

The last step is justified by $f(x) = x+\sqrt{x^2-1}$ being a monotonically increasing function, for the relevant domain $x \ge1$. We can see this by noting the gradient $\frac{d}{dx}(x+\sqrt{x^2-1}) = \frac{x}{\sqrt(x^2 - 1)} + 1$ is always positive for $x > 1$.

Exercise (8.3).12

Prove the following:

If $r = a + b\sqrt{N}$ produces a solution of Pell’s equation $x^2 − Ny^2 = 1$ then so does $r^n = (a + b\sqrt{N})^n$, where $n$ is any integer.

There are three cases for $n$, which are $n>0$, $n=0$ and $n<0$. Let's consider each case in turn.

Case $n>0$

We proved this case in the previous Exercise (8.3).12.

Case $n=0$

We have

$$ r^n = (a+b\sqrt{N})^0 = 1 = 1 + 0\sqrt{N}$$

This produces the solution $(x,y)=(1,0)$ which is indeed a solution to $x^2-Ny^2=1$.

Case $n<0$

We interpret negative indices to mean the multiplicative inverse as follows

$$ r^{-m} \times r^m = 1 $$

for some natural number $m$.

Writing $r^m=a+b\sqrt{N}$ and $r^{-m}=\alpha + \beta \sqrt{N}$, we have

$$  \begin{align} 1 & = (a+b\sqrt{N}) \times (\alpha + \beta \sqrt{N}) \\ \\ & = a \alpha + a \beta \sqrt{N} + b \alpha \sqrt{N} + b \beta N^2 \\ \\ 1 + 0 \sqrt{N} & = (a \alpha + b \beta N^2) + (a \beta + b \alpha)\sqrt{N} \end{align}$$

This means

$$ a \alpha + b \beta N^2 = 1 \tag{i}$$

$$ a \beta + b \alpha = 0 \tag{ii}$$

Since $r^m$ produces a solution to Pell's equation, we also have

$$ a^2 -Nb^2 = 1 \tag{iii}$$

We aim to show that $\alpha^2 - N \beta^2 =1$.

We start by multiplying (i) by $b$, 

$$ \begin{align} a \alpha b + b^2 \beta N^2 & = b \\ \\  \beta(a^2 - b^2  N^2) &= -b \tag{using (ii)} \\ \\ \beta &= - b \tag{(iv) using (iii)}\end{align} $$

We proceed by multiplying (i) by $\beta$, 

$$ \begin{align} a \alpha \beta + b \beta^2 N^2 & = \beta \\ \\  b (\beta^2 N^2 - \alpha^2) & = \beta  \tag{using (ii)} \\ \\  \beta ( \alpha^2 - \beta^2 N^2) & = \beta \tag{using (iv)}\\ \\ \alpha^2 - \beta^2 N^2 & = 1 \end{align} $$

And so we have shown that $r^{n}$, where $n<0$, produces a solution to $x^2 -Ny^2=1$.

By showing that all the cases $n>0, n=0, n<0$ lead to $r^n$ producing a solution to $x^2-Ny^2=1$, where $r$ produces a solution, we have shown $r^n$ does for any integer.

Exercise (8.3).11

Prove Proposition (8.19).

Let's remind ourselves of Proposition (8.19). 

If $r = a + b\sqrt{N}$ produces a positive solution of Pell’s equation $x^2− Ny^2 = 1$ then so does $r^n = (a + b\sqrt{N})^n = \alpha + \beta \sqrt{N}$ where $n = 1, 2, 3, \ldots$.

We will prove the statement by induction. 

Let $P(n)$ be the statement that $r^n=(a+b\sqrt{N})^n$ produces a positive solution of $x^2-Ny^2=1$, under the assumption that $r = a + b\sqrt{N}$ does.

We need to prove a base case $P(1)$ and the induction step $P(n) \implies P(n+1)$.

Base Case

The base case is the statement that $r^1=(a+b\sqrt{N})^1$ produces a positive solution to $x^2-Ny^2=1$. This is trivially true because of the assumption that $r = a + b\sqrt{N}$ does.

Induction Step

Assuming $r^n$ produces a positive solution, we need to show that $r^{n+1}$ produces a positive solution.

The induction hypothesis is that $r^n=(\alpha+\beta \sqrt{N})$ produces a positive solution. That is, $\alpha^2 -N \beta^2 = 1$.

We proceed as follows,

$$ \begin{align} r^{n+1} = r^n \times r & = (\alpha + \beta \sqrt{N})\times(a+b\sqrt{N}) \\ \\  & = \alpha a + \alpha b \sqrt{N} + \beta a \sqrt{N}  + \beta  b N \\ \\ & = (\alpha a + \beta b N) + (\alpha b + \beta a)\sqrt{N} \end{align} $$

We need to show that $(\alpha a + \beta b N)^2 - N(\alpha b + \beta a)^2 = 1$.

$$ \begin{align}(\alpha a + \beta b N)^2 - N(\alpha b + \beta a)^2  & = a^2 \alpha^2 + \cancel{2 a \alpha b \beta N} + b^2 \beta^2 N^2 - (a^2 \beta^2 N + \cancel{2 a \alpha b \beta N} + \alpha^2 b^2 N) \\ \\ & = \alpha^2\underbrace{(a^2 - N b^2)}_{=1} - N\beta^2\underbrace{(a^2 - N b^2)}_{=1} \\ \\ & = \alpha^2 - N \beta^2 \\ \\ & = 1 \quad \text{(by induction hypothesis)}  \end{align} $$

So $r^{n+1}$ produces a solution, and is a positive solution because $x=(\alpha a + \beta b N)^2$ and $y=(\alpha b + \beta a)^2$ are positive.

By induction we have proved the Proposition (8.19).

Exercise (8.3).10

Prove identity (8.16).

Let's remind ourselves of Proposition (8.16).  For integers $a$, $b$, $c$, $d$, and $N$ we have the identity:

$$ (a^2 − Nb^2) (c^2 − Nd^2) = (ac + Nbd)^2 − N (ad + bc)^2 $$

We expand the LHS:

$$ (a^2 − Nb^2) (c^2 − Nd^2) = a^2 c^2 - a^2 d^2 N - b^2 c^2 N + b^2 d^2 N^2 $$

Similarly we expand the RHS:

$$ (ac + Nbd)^2 − N (ad + bc)^2  = a^2 c^2 - a^2 d^2 N - b^2 c^2 N + b^2 d^2 N^2$$

Since LHS=RHS, the identity is proven.

Exercise (8.3).9

Check that $r = 55 + 12\sqrt{21}$ produces the least positive solution of

$$x^2− 21y^2 = 1$$

Determine two more positive solutions of $x^2 − 21y^2 = 1$.

The following table confirms that values of $y$ in the range $[1,11]$ do not produce integer solutions for $x$.

y	1+21*y^2	x=sqrt(1+21*y^2)
1	22	4.69041575982343
2	85	9.21954445729289
3	190	13.7840487520902
4	337	18.3575597506858
5	526	22.9346898823594
6	757	27.5136329843952
7	1030	32.0936130717624
8	1345	36.6742416417845
9	1702	41.2553026894725
10	2101	45.8366665454634
11	2542	50.4182506638221
12	3025	55

And so $(x,y)=(55,12)$ is the least positive solution.

Two further solutions are $r^2$ and $r^3$. 

$$ r^2 = 6049 + 1320 \sqrt(21) $$

$$r^3 = 665335 + 145188 \sqrt{21}$$

And so two further positive solutions are $(x,y)=(6049,1320)$ and $(x,y)=(665335, 145188)$.

Exercise (8.3).8

Show that if $N > 0$ is a square number then $x^2− Ny^2 = 1$ only has trivial solutions: $x = 1, y= 0$ or $x = −1, y= 0$.

If $N>0$ is a square number then we can write it as $N=n^2$ for some natural number $n>0$. 

And so

$$ x^2 - (ny)^2 = 1 $$

The difference of two squares gives

$$ (x-ny)(x+ny) = 1 $$

The product is only 1 if the factors are both 1 or both -1. 

If both factors are 1, we have 

$$ x - ny = 1 \; \land \; x + ny = 1 \implies x = 1, y = 0$$

If both factors are -1, we have 

$$ x - ny = -1 \; \land \; x + ny = -1 \implies x = -1, y = 0$$

Exercise (8.3).7

Determine three different solutions of

$$ x^2− 47y^2 = 1 $$

We first try to find the least positive solution by trying the smallest values of $y$.

Trying $y=1,2,3,4,5,6$ does not give a natural number solution for $x$. The first solution is $y=7, x=48$.

From the least positive solution $r=47+7\sqrt{47}$, we can generate two further solutions $r^2$ and $r^3$.

$$ r^2 =  4607 + 672 \sqrt{47}$$

$$ r^3 = 442224 + 64505 \sqrt{47} $$

So three solutions are $(x,y)=(48,7)$, $(x,y)=(4607,672)$ and $(x,y)=(442224, 64505 )$.

Exercise (8.3).6

(i) Check that $r = 17 + 12\sqrt{2}$ yields a solution of $x^2 − 2y^2 = 1$.

(ii) Hence or otherwise find a solution of $u^2− 8v^2 = 1$.

(iii) Hence or otherwise find a solution of $u^2 − 32v^2 = 1$.

(iv) Determine the condition on $m$ for $u^2− 2 (mv)^2 = 1$ to have a solution.

(i) From $r=17 + 12\sqrt{2}$ we have $x=17$ and $y=12$.

$$ x^2 -2y^2 = 17^2 -2(12^2) = 289 - 288 = 1 $$

So $r=17 + 12\sqrt{2}$ is a solution to $x^2 − 2y^2 = 1$.

(ii) We write $u^2− 8v^2 = 1$ as $u^2− 2(2v)^2 = 1$. 

We have the solution $u=17, 2v=12$, which is $u=17, v=6$.

(iii) We write $u^2− 32v^2 = 1$ as $u^2− 2(4v)^2 = 1$. 

We have the solution $u=17, 4v=12$, which is $u=17, v=3$.

(iv) From the solution $(17,12)$ we have $mv=12$, so the condition on $m$ is that it is a factor of 12.

Exercise (8.3).5

Show that if $N=n^2− 1$ where $n$ is a natural number then the least positive solution of $x^2− Ny^2 = 1$ is given by $x = n, y= 1$.

Determine the least positive solutions of $x^2 − Ny^2 = 1$ where

(a) $N = 15$

(b) $N = 24$

(c) $N = 35$

(d) $N = 48$

We proceed as follows

$$ x^2 - Ny^2 = x^2 - (n^2-1)y^2 = 1 $$

If $y=1$ then a solution is a candidate for the least positive solution. Let's try it

$$ x^2 - n^2 + 1 = 1 \quad \implies \quad x = n $$

So $(x,y) = (n,1)$ is a solution.

We need to check that $x=1$ isn't part of a least positive solution. We will use  Proposition (8.20),

Let $r = a + b\sqrt{N}$ and $s = c + d\sqrt{N}$ both produce positive solutions of Pell’s equation $x^2− Ny^2 = 1$. Then $r < s \iff a < c$. 

For the purpose of contradiction let's assume a positive solution $a+b\sqrt{N}$ exists and is smaller than the known solution $n+\sqrt{N}$, that is, $a+b\sqrt{N}<n+\sqrt{N}$. By Proposition (8.20) this means $a<n$. From $a^2 - Ny^2=1$ we have $1+(n^2-1)y^2<n^2$, which gives $y^2<\frac{n^2-1}{n^2-1}=1$. This is a contradiction because $y$ must be greater than or equal to 1. And so there is no smaller solution than $n+\sqrt{N}$.

And so $(x,y)=(n,1)$ is a solution, and is the least positive solution.

(a) Since $15=4^2-1$ we have the least positive solution $(x,y) = (4,1)$.

(b) Since $24=5^2-1$ we have the least positive solution $(x,y) = (5,1)$.

(c) Since $35=6^2-1$ we have the least positive solution $(x,y) = (6,1)$.

(d) Since $48=7^2-1$ we have the least positive solution $(x,y) = (7,1)$.

Exercise (8.3).4

(i) By using your $r = 3 + 2\sqrt{2}$ of Example 8.10, determine $r^2$, $r^3$, and $r^4$. Check that these also yield solutions of $x^2 − 2y^2 = 1$.

(ii) Find approximations of $\sqrt{2}$ by using $r$, $r^2$, $r^3$, and $r^4$ and the discrepancy between $\sqrt{2}$ and your approximations correct to 3 significant figures.

(iii) Explain why the solutions to the equation $x^2 − 2y^2 = 1$ give rational approximations to $\sqrt{2}$.

(i) We start with

$$ r = 3 + 2\sqrt{2} $$

For $r^2$ we have

$$ r^2 = 3^2 + 2^2(2) + 3 \cdot 3 \cdot 2\sqrt{2} = 17 + 12\sqrt{2} $$

Validating $(x,y)=(17,12)$ is a solution

$$ 17^2 - 2(12^2) = 289 - 288 = 1$$

For $r^3$ we have

$$ r^3 = (3+2\sqrt{2})(17+12\sqrt{2}) = 51 + 24\cdot2 + 3\cdot12\sqrt{2} + 17\cdot2\sqrt{2} = 99 + 70\sqrt{2}$$

Validating $(x,y)=(99,70)$ is a solution

$$ 99^2 - 2(70^2) = 9801 - 9800 = 1 $$

For $r^4$ we have

$$r^4 = (r^2)^2 = (17+12\sqrt{2})^2 = 289 + 144\cdot2 + 2\cdot17\cdot12\sqrt{2} = 577 + 408\sqrt{2}$$

Validating $(x,y)=(577,408)$ is a solution

$$ 577^2 - 2(408^2) = 332929 - 332928 = 1$$

(ii) The following table shows approximations for $\sqrt{2}$ using $\frac{x}{y}$.

r^n	x	y	x/y	x/y – sqrt(2)
r	3	2	1.5	8.58E-02
r^2	17	12	1.41666666666667	2.45E-03
r^3	99	70	1.41428571428571	7.22E-05
r^4	577	408	1.41421568627451	2.12E-06

The approximations improve as the power of $r$ grows.

(iii) Re-arranging $x^2-2y^2=1$ gives

$$ \frac{x}{y} = \sqrt{2+\frac{1}{y^2}} $$

And so the rational number $\frac{x}{y}$ better approximates $\sqrt{2}$ as $y$ grows larger. The solutions produced by $r^n$ as $n$ grows larger have larger values of $y$.

Exercise (8.3).3

(a) (i) Show that $r = 577 + 408\sqrt{2}$ produces a solution of $x^2 − 2y^2 = 1$.

(ii) Determine a rational approximation to $\sqrt{2}$ using $r$ of part (i).

What is the discrepancy between your approximation and $\sqrt{2}$?

(iii) Show that $\frac{x}{y} =\sqrt{2+\frac{1}{y^2}}$ gives an approximation to $\sqrt{2}$.

To get a good approximation to $\sqrt{2}$ what condition do you need your solution to satisfy?

(b) Let $x$ and $y$ be solutions of $x^2 − Ny^2 = 1$. Show that $\frac{x}{y} =\sqrt{2+\frac{1}{y^2}}$ gives an approximation of $\sqrt{N}$. 

The Greek mathematician Archimedes used this to find approximations for $\sqrt{N}$.

(a) 

(i) $r = 577 + 408\sqrt{2}$ gives $x=577$ and $y=408$, and we verify as follows

$$ x^2 - 2y^2 = 577^2 -2(408)^2 = 332929 - 332928 = 1 $$

(ii) From $x^2 - 2y^2 =1$ we have $\frac{x^2-1}{y^2}=2$. Approximating $x^2-1 \approx x^2$ gives us $\frac{x}{y} \approx \sqrt{2}$. 

And so a rational approximation for $\sqrt{2}$ is $\frac{577}{408}$.

The discrepancy is 0.00000212, or approximately 1 part in 471,000.

(iii) We start by re-arranging $x^2 - 2y^2 = 1$,

$$\begin{align} \frac{x^2}{y^2} - 2 & = \frac{1}{y^2} \\ \\  \frac{x^2}{y^2} & = 2 +  \frac{1}{y^2} \\ \\ \frac{x}{y} & = \sqrt{2 +  \frac{1}{y^2}} \end{align}$$

The larger $y$ is, the better the approximation of $\sqrt{2}$. 

(b) We start by re-arranging $x^2 - Ny^2 = 1$,

$$\begin{align} \frac{x^2}{y^2} - N & = \frac{1}{y^2} \\ \\  \frac{x^2}{y^2} & = N +  \frac{1}{y^2} \\ \\ \frac{x}{y} & = \sqrt{N +  \frac{1}{y^2}} \end{align}$$

As $y$ gets larger, the approximation gets better.

Exercise (8.3).2

Check that $r = 649 + 180\sqrt{13}$ produces a solution of $x^2 − 13y^2 = 1$.

Determine another positive solution of this equation $x^2 − 13y^2 = 1$.

From $r=649+180\sqrt{13}$ we have $x=649$ and $y=180$. 

$$ x^2 - 13y^2 =  649^2 - 13(180)^2 = 421201 - 421200 = 1$$

By Theorem (8.21) all other positive solutions are produced by $r^n$, where $n$ is a natural number. We can try $n=2$.

$$ r^2 = (649+180\sqrt{13})^2 = 842401 + 233640\sqrt{13} $$

That is $(x,y)=(842401, 233640)$. 

Let's verify this solution

$$ x^2 - 13y^2 = 842401^2 - 13(233640)^2 =  709639444801 - 709639444800 = 1$$

Exercise (8.3).1

Determine the least positive solution for the following values of $N$ in Pell’s equation

$$ x^2 − Ny^2 = 1$$ 

by substituting appropriate integer values for $y$:

(a) $N = 3$

(b) $N = 7$

(c) $N = 8$

(d) $N = 11$

(e) $N = 10$

(f) $N = 12$

The approach is trial and error, starting with the smallest candidate solutions.

(a) $x^2 - 3y^2 = 1$

We try $y=1$, which immediately gives us $x=2$. So the solution is $(x,y)=(2, 1)$.

(b) $x^2 - 7y^2 = 1$

$y=1, 2$ doesn't give us a perfect square for $1+7y^2$. $y=3$ works and gives a solution $(x,y)=(8, 3)$.

(c) $x^2 - 8y^2 = 1$

$y=1$ immediately gives a solution $(x,y)=(3, 1)$.

(d) $x^2 - 11y^2 =1$

$y=1, 2$ doesn't give us a perfect square for $1+11y^2$. $y=3$ works and gives us $(x,y)=(10, 3)$.

(e) $x^2 - 10y^2 = 1$

$y = 1, 2, 3, 4, 5, $ do not give us a perfect square for $1+10y^2$. $y=6$ gives us $(x,y)=(19, 6)$.

(f) $x^2 - 12y^2=1$

$y=1$ does not give us a perfect square for $1+12y^2$. $y=2$ gives $(x,y) = (7,2)$.

Exercise (8.2).14

Prove Theorem (8.13).

Let's remind ourselves of Theorem (8.13). 

Every prime can be expressed as the sum of four squares.

---

We'll first prove a Lemma A:

If an even number $2n$ is the sum of four squares, so is $n$.

We write $2n=x^2 + y^2 + s^2 + t^2 $ where $x,y,s,t$ are natural numbers.

Because $2n$ is even, there are only 3 cases for these summands:

• all four summands are even
• all four summands are odd
• two are even, two are odd

Without loss of generality, let's assume that $x^2$ and $y^2$ have the same parity, and that $s^2$ and $t^2$ have the same parity. Noting that a number has the same parity as its square, and the the sum and difference of two numbers with the same parity gives an even integer, we have for some integers $j,k, l, m$, 

$$ \begin{align} 2n = x^2 + y^2 + s^2 + t^2 & = \frac{(x+y)^2+(x-y)^2}{2}  +  \frac{(s+t)^2+(s-t)^2}{2} \\ \\ & = \frac{(2j)^2+(2k)^2}{2} +  \frac{(2l)^2+(2m)^2}{2} \\ \\ & = 2j^2 + 2k^2 + 2l^2 + 2m^2 \\ \\  n & = j^2 + k^2 + l^2 + m^2 \end{align} $$

That is, if an even number $2n$ is the sum of four squares, so is $n$.

---

We first consider the only even prime 2, which can be written as the sum of four squares $2=1^2 + 1^2 +0^2 +0^2$. 

We now consider the odd primes. Corollary (8.12) tells us that for any odd prime $p$ there exists a positive $m<p$ such that $mp$ can be expressed as the sum of four squares. That is, for some natural numbers $a,b,c,d$,

$$ mp = a^2 + b^2 + c^2 + d^2 $$

For the purpose of contradiction, let's assume $m$ is the minimal possible value. If we can find a natural number $1 \le n<m$ such that $np$ can be expressed as the sum of four squares, then we contradict that $m$ is the minimal possible value such that $mp$ can be expressed as a sum of four squares.

There are two cases for $m$, even and odd. 

Case $m$ even

For the case $m$ is even, Lemma A tells us that $n=m/2$ can also be expressed as sum of four squares. So we have found an $n<m$ such that $np$ can be expressed as the sum of four squares, contradicting that $m$ is the minimal possible value.

Case $m$ odd

For the case $m$ is odd, we carefully choose

$$ \begin{align} a' & \equiv a \pmod m \\  b' & \equiv b \pmod m \\ c' & \equiv c \pmod m \\ d' & \equiv d \pmod m \end{align} \tag{i}$$

where each of the $a', b', c', d'$ are in the interval $(-m/2, m/2)$.

None of $a', b', c', d'$ can be $m/2$ because $m$ is odd and $m/2$ is not an integer. Similarly all $a', b', c', d'$ cannot be 0, since that would mean all of $a, b, c, d$ are multiples of $m$, leading to $m^2 \mid a^2 + b^2 + c^2 + d^2 = mp$, and the implied $m \mid p$, and requiring $m=p$ since $p$ is prime, but contradicting $m<p$.

And so, for $m>1$,

$$ 0 < a'^2 + b'^2 + c'^2 + d'^2 \; < \; 4 (\frac{m}{2})^2 \; = \; m^2 $$

Also, 

$$  a'^2 + b'^2 + c'^2 + d'^2 \equiv a^2 + b^2 + c^2 + d^2 \equiv 0 \pmod m  \tag{ii}$$

which means $a'^2 + b'^2 + c'^2 + d'^2 = nm$ for some natural number $n$. Since $0 < a'^2 + b'^2 + c'^2 + d'^2 < m^2$, that means

$$0 < n<m $$

Applying the Sum of Four Squares Identity (8.10) to the product $(a'^2 \times b'^2 \times c'^2 \times d'^2) \times (a^2 \times b^2 \times c^2 \times d^2)$ gives

$$  \begin{align} (a'^2 \times b'^2 \times c'^2 \times d'^2) \times (a^2 \times b^2 \times c^2 \times d^2) & =  (a'a + b'b + c'c + d'd)^2  + (a'c− b'd− c'a + d'b)^2 \\  & + (a'b− b'a + c'd− d'c)^2  + (a'd + b'c− c'c− d'a)^2 \end{align} $$

The congruences in (i) and (ii) above tell us each of $ (a'a + b'b + c'c + d'd)$, $(a'c− b'd− c'a + d'b)$, $(a'b− b'a + c'd− d'c)$, and $(a'd + b'c− c'c− d'a)$ are congruent to 0 modulo $m$. That is, each is divisible by $m$. And so, 

$$  \begin{align} n\cancel{m} \times \cancel{m}p & =  (\frac{a'a + b'b + c'c + d'd}{m})^2  + (\frac{a'c− b'd− c'a + d'b}{m})^2 \\  & + (\frac{a'b− b'a + c'd− d'c}{m})^2  + (\frac{a'd + b'c− c'c− d'a}{m})^2 \\ \\ np & =  (\frac{a'a + b'b + c'c + d'd}{m})^2  + (\frac{a'c− b'd− c'a + d'b}{m})^2 \\  & + (\frac{a'b− b'a + c'd− d'c}{m})^2  + (\frac{a'd + b'c− c'c− d'a}{m})^2 \ \end{align} $$

We have shown that $np$ can be expressed as a sum of squares, and $n<m$ which contradicts the minimality of $m$. 

We have shown that for any $m$ such that $mp$ is expressible as a sum of four squares, we can always find a smaller $n$ such that $np$ is expressible as a sum of squares, unless $m=1$. 

In totality, we have shown that any prime can be expressed as a sum of four squares.

Exercise (8.2).13

Prove Sum of Four Squares Identity (8.10).

The Sum of Four Squares Identity (8.10) is

$$ \begin{align} (a^2 + b^2 + c^2 + d^2) \times (x^2 + y^2 + z^2 + w^2) & = (ax + by + cz + dw)^2  + (az− bw− cx + dy)^2 \\ \\ & + (ay− bx + cw− dz)^2  + (aw + bz− cy− dx)^2 \end{align} $$

We'll expand the LHS first:

$$\begin{align}  (a^2 + b^2 + c^2 + d^2) \times (x^2 + y^2 + z^2 + w^2) & = a^2 w^2 + a^2 x^2 + a^2 y^2 + a^2 z^2  \\ & + b^2 w^2 + b^2 x^2 + b^2 y^2 + b^2 z^2  \\ & + c^2 w^2 + c^2 x^2 + c^2 y^2 + c^2 z^2  \\ & + d^2 w^2 + d^2 x^2 + d^2 y^2 + d^2 z^2 \end{align}$$

We'll expand the RHS first:

$$\begin{align} (ax + by + cz + dw)^2  + (az− bw− cx + dy)^2 + \\ (ay− bx + cw− dz)^2  + (aw + bz− cy− dx)^2 & = a^2 x^2 + 2 a b x y + 2 a c x z + 2 a d w x \\ & + b^2 y^2 + 2 b c y z + 2 b d w y  \\ &+ c^2 z^2 + 2 c d w z + d^2 w^2 \\ & + a^2 z^2 - 2 a b w z - 2 a c x z + 2 a d y z \\ & + b^2 w^2 + 2 b c w x - 2 b d w y \\ & + c^2 x^2 - 2 c d x y + d^2 y^2 \\ & +  a^2 y^2 - 2 a b x y + 2 a c w y - 2 a d y z \\ &+ b^2 x^2 - 2 b c w x + 2 b d x z \\ & + c^2 w^2 - 2 c d w z + d^2 z^2 \\ & + a^2 w^2 + 2 a b w z - 2 a c w y - 2 a d w x \\ & + b^2 z^2 - 2 b c y z - 2 b d x z \\ & + c^2 y^2 + 2 c d x y + d^2 x^2  \\ \\ & = a^2 w^2 + a^2 x^2 + a^2 y^2 + a^2 z^2 \\ & + b^2 w^2 + b^2 x^2 + b^2 y^2 + b^2 z^2 \\ & + c^2 w^2 + c^2 x^2 + c^2 y^2 + c^2 z^2 \\ & + d^2 w^2 + d^2 x^2 + d^2 y^2 + d^2 z^2 \end{align}$$

The LHS is the same as the RHS and so the identity is proven.

Exercise (8.2).12

Prove Proposition (8.9).

Let's remind ourselves of Proposition (8.9).

A positive integer which looks like $4^n (8m + 7)$ cannot be expressed as a sum of three squares.

For the purpose of contradiction, let's assume $4^n(8m+7)$ can be expressed as a sum of three squares.

$$ 4^n(8m+7) = a^2 + b^2 + c^2 + d^2 $$

Noting that $4^n = (2^n)^2$, we have

$$ (2^n)^2(8m+7) = a^2 + b^2 + c^2 + d^2 $$

That is, $2^n$ is a factor of each $a, b, c, d$. This means $\frac{a}{2^n}, \frac{b}{2^n}$, etc are whole numbers.

And so

$$ 8m+7 = (\frac{a}{2^n})^2 + (\frac{b}{2^n})^2 + (\frac{c}{2^n})^2 + (\frac{d}{2^n})^2 $$

This means a natural number of the form $8m+7$ can be expressed as a sum of four squares. However, from the last excericse (8.2).11 we know that $8m+7$ can not be expressed as a sum of four squares.

This contradiction tells us the assumption $4^n(8m+7)$ can be expressed as a sum of three squares is false, proving the Proposition (8.9).

Exercise (8.2).11

Prove that $8m + 7$ cannot be written as a sum of three squares.

For a given natural number $n$, let's consider its square $n^2 \pmod 8$. There are two cases to consider, even $n=2x$ and odd $n=2x+1$, for some natural number $x$.

Case even $n=2x$

We have $ n^2 = (2x)^2 = 4x^2 $.

Now $x$ can itself be even $x=2y$ or odd $x=2y+1$, for some natural number $y$. 

If $x$ is even then $n^2 = 4(2y)^2 = 16y^2$, and so $n^2 \equiv 0 \pmod 8$.

If $x$ is odd then $n^2 = 4(2y+1)^2 = 4(4y^2 +4y +1) = 16y^2+16y+4$, and so $n^2 \equiv 4 \pmod 8$.

Case odd $n=2x+1$

We have $ n^2 = (2x+1)^2 = 4x^2 + 4x + 1$.

Now $x$ can itself be even $x=2y$ or odd $x=2y+1$, for some natural number $y$. 

If $x$ is even then $n^2 = 4(2y)^2 + 4(2y) + 1 = 16y^2 + 8y + 1$, and so $n^2 \equiv 1 \pmod 8$.

If $x$ is odd then $n^2 = 4(2y+1)^2 + 4(2y+1) + 1 = 4(4y^2 + 4y + 1) + 8y + 4  + 1 = 16y^2+16y + 8y + 8 + 1$, and so $n^2 \equiv 1 \pmod 8$.

In all cases the square of a natural number is only 0, 1 or 4 modulo 8. This means the sum of 3 squares can only be 0, 1, 2, 3, 4, 5, 6, but never 7. This means the sum of 2 squares can't take the form $8m+7$.

Exercise (8.2).10

Show that expressing a positive integer into sum of four squares is not unique.

Consider the positive integer 169. We have

$$ 169 = 1^2 + 2^2 + 8^2 + 10^2 $$

$$ 169 = 2^2 + 4^2 + 7^2 + 10^2 $$

$$ 169 = 4^2 + 4^2 + 4^2 + 11^2 $$

$$ 169 = 4^2 + 5^2 + 8^2 + 8^2 $$

$$ 169 = 4^2 + 6^2 + 6^2 + 9^2 $$

And so we have shown that expressing a positive integer into a sum of four squares is not unique by providing a counter-example.

Exercise (8.2).9

Let $n > 169$ be an integer. Show that $n$ can be written as the sum of five positive squares. 

Hint: Consider $n = m + 169$.

Note, a positive square is greater than 0, that is, not 0^2.

By Lagrange’s Sum of Four Squares Theorem (8.14), we know that every positive integer can be expressed as a sum of four squares (some of which can be zero).

And so we can write a positive integer $m$ as

$$ m = a^2 + b^2 + c^2 + d^2 $$

We define $n=m+169$, and noting that $169=13^2$

$$ n = a^2 + b^2 + c^2 + d^2 + 13^2 $$

We now consider the cases where some of $a,b,c,d$ are 0:

• One of  $a,b,c,d$ is 0. Without loss of generality, $d=0$.
• Two of  $a,b,c,d$ are 0. Without loss of generality, $c=d=0$.
• Three of  $a,b,c,d$ are 0. Without loss of generality, $b=c=d=0$.

All four $a,b,c,d$ can't be zero because this would give $n=169$ which contradicts $n>169$. Let's consider each case in turn.

Case One

We have, noting that $13^2 = 12^2 + 5^2$

$$ n = a^2 + b^2 + c^2 + 0^2 + (13^2) = a^2 + b^2 + c^2 + 12^2 + 5^2 $$

In this case $n$ can be expressed as the sum of five positive squares.

Case Two

We have, noting that $13^2 = 3^2 + 4^2 + 12^2$

$$ n = a^2 + b^2 + 0^2 + 0^2 + (13^2) = a^2 + b^2 +3^2 + 4^2 + 12^2 $$

In this case $n$ can be expressed as the sum of five positive squares.

Case Three

We have, noting that $13^2 = 1^2 + 2^2 + 8^2 +10^2$

$$ n = a^2 + 0^2 + 0^2 + 0^2 + (13^2) = a^2 + 1^2 + 2^2 + 8^2 +10^2 $$

In this case $n$ can be expressed as the sum of five positive squares.

In all cases we have shown that $n$ can be expressed as the sum of five positive squares.

Exercise (8.2).8

If $x = a^2 + b^2 + c^2 + d^2$, show that 

$$ 2x = (a + b)^2 + (a− b)^2 + (d− c)^2 + (c + d)^2 $$

Given $1984 = 40^2 + 16^2 + 8^2 + 8^2$, convert

(i) $3968 = 2 \times 1984$ into sum of four squares.

(ii) $992 = \frac{1984}{2}$ into sum of four squares. Hint: Use part (i).

We proceed as follows

$$  \begin{align} (a + b)^2 + (a− b)^2 + (d− c)^2 + (c + d)^2 & = a^2 + b^2 +\cancel{2ab} + a^2 +b^2 -\cancel{2ab} +d^2 +c^2 -\cancel{2cd} + c^2 + d^2 + \cancel{2cd} \\ \\ & = 2(a^2 + b^2 + c^2 + d^2) \\ \\ & = 2x \end{align}$$

(i) We have $1984 = 40^2 + 16^2 + 8^2 + 8^2$, and so

$$ \begin{align} 3968 & = 2 \times 1984 \\ \\ & = 2 \times (40^2 + 16^2 + 8^2 + 8^2) \\ \\ & = (40+16)^2 + (40-16)^2 + (8-8)^2 + (8+8)^2 \\ \\ & = 56^2 + 24^2 + 16^2  \end{align} $$

(ii) We proceed as follows

$$ \begin{align} 992 & = \frac{1984}{2} \\ \\ & =  \frac{2(40^2 + 16^2 + 8^2 + 8^2)}{2^2} \\ \\ & = \frac{56^2 + 24^2 + 16^2}{2^2} \\ \\ & = 28^2 + 12^2 + 8^2 \end{align} $$

Exercise (8.2).7

Determine all the incongruent solutions of

$$ x^2 + y^2 \equiv −1 \pmod {13} $$

The following table shows the calculations of $n^2 \pmod {13}$ and $-1-n^2 \pmod {13}$.

n	n^2 mod 13	-1-n^2 mod 13
0	0	12
1	1	11
2	4	8
3	9	3
4	3	9
5	12	0
6	10	2
7	10	2
8	12	0
9	3	9
10	9	3
11	4	8
12	1	11

We can read all the solutions $(x,y)$ to $x^2 + y^2 \equiv -1 \pmod {13}$ as follows

$$ (3, 4), (3, 9), (10, 4), (10, 9) $$

$$ (4, 3), (4, 10), (9, 3), (9, 10) $$

$$ (5, 0), (8, 0) $$

$$ (0,5), (0,8) $$

Exercise (8.2).6

Find all the incongruent solutions of

$$ x^2 + y^2 \equiv −1 \pmod {19} $$

See Example 8.7.

The following table shows the calculation of $n^2 \pmod {19}$ and $-1-^2 \pmod {19}$ for $0 \le n \le 18$.

n	n^2 mod 19	-1-n^2 mod 19
0	0	18
1	1	17
2	4	14
3	9	9
4	16	2
5	6	12
6	17	1
7	11	7
8	7	11
9	5	13
10	5	13
11	7	11
12	11	7
13	17	1
14	6	12
15	16	2
16	9	9
17	4	14
18	1	17

We can read off the pairs of solutions $(x,y)$ to $x^2 \equiv -1 - y^2 \pmod {19}$ as follows:

$$ (1, 6), (1, 13), (18, 6), (18, 13) $$

$$ (3, 3), (3, 16), (16,3), (16,16) $$

$$ (6, 1), (6, 18), (13, 1), (13, 18) $$

$$ (7, 8), (7, 11), (12, 8), (12, 11) $$

$$ (8, 7), (8, 12), (11, 7), (11, 12) $$

The authors solution takes the previously determined solutions $(x,y)$ and uses that if $a$ is a solution so is $-a$, to generate additional solutions $(-x,y), (x, -y), (-x, -y)$.

Exercise (8.2).5

Convert the following into sum of four squares:

(a) $6a^2b^2$

(b) $7a^2b^2$

(c) $na^2b^2$

where $n$ is a positive integer.

We'll be using the Sum of Four Squares Identity (8.10) is

$$ \begin{align} (a^2 + b^2 + c^2 + d^2) \times (x^2 + y^2 + z^2 + w^2) & = (ax + by + cz + dw)^2  + (az− bw− cx + dy)^2 \\ \\ & + (ay− bx + cw− dz)^2  + (aw + bz− cy− dx)^2 \end{align} $$

(a) 

$$ 6a^2b^2 = (2^2 + 1^2 +1^2) \times (ab)^2 = (2ab)^2 + (ab)^2 + (ab)^2$$

(b) 

$$ 7a^2b^2 = (2^2 + 1^2 +1^2 + 1^2) \times (ab)^2 = (2ab)^2 + (ab)^2 + (ab)^2 + (ab)^2 $$

(c) Since $n$ is a positive integer, Lagrange’s Sum of Four Squares Theorem (8.14), it can be written as the sum of four squares,

$$ n = n_1^2 + n_2^2 + n_3^2 + n_4^2 $$

And so

$$ na^2b^2 = (n_1^2 + n_2^2 + n_3^2 + n_4^2) \times (ab)^2 = (n_1ab)^2 + (n_2ab)^2 + (n_3ab)^2 + (n_4ab)^2  $$

Exercises (8.2).4

Convert the following into sum of four squares:

(i) $343= 7^3$

(ii) $2401= 7^4$

(iii) $16 807= 7^5$

Determine a formula for converting $7^n$, where $n$ is a natural number, to sum of four squares.

Let $x = a^2 + b^2 + c^2 + d^2$. Determine a formula for converting $x^n$ into sum of four squares.

We'll be using the Sum of Four Squares Identity (8.10) is

$$ \begin{align} (a^2 + b^2 + c^2 + d^2) \times (x^2 + y^2 + z^2 + w^2) & = (ax + by + cz + dw)^2  + (az− bw− cx + dy)^2 \\ \\ & + (ay− bx + cw− dz)^2  + (aw + bz− cy− dx)^2 \end{align} $$

(i) $ 343 = 7^2 \times 7 = (7^2 + 0^2 + 0^2 + 0^2) \times (2^2 + 1^2 + 1^2 + 1^2) = 14^2 + 7^2 + 7^2 + 7^2 $

(ii) $ 2401 = 7^2 \times 7^2 = (7^2 + 0^2 + 0^2 + 0^2) \times (7^2 + 0^2 + 0^2 + 0^2) = 49^2 $

(iii) $ 16807 = 7^4 \times 7 = (49^2 + 0^2 + 0^2 + 0^2) \times (2^2 + 1^2 + 1^2 + 1^2) = 98^2 + 49^2 + 49^2 + 49^2$

---

We consider two cases for $n$ in $7^n$, even $n=2m$ and odd $n=2m+1$ for some integer $m$.

For even $n=2m$ we have

$$ 7^n = 7^{2m} = (7^m)^2 $$

For odd $n=2m+1$ we have

$$ 7^n = 7^{2m+1} = (7^m)^2 \times (2^2 + 1^2 + 1^2 + 1^2) =  (2 \times 7^m)^2 + (7^m)^2 + (7^m)^2 + (7^m)^2)  $$

In summary,

$$ 7^n = \begin{cases} (7^m)^2 & \text{even } n=2m \\ \\  (2 \times 7^m)^2  + (7^m)^2 + (7^m)^2  + (7^m)^2 & \text{odd } n=2m+1 \end{cases} $$

---

We again consider 2 cases for $n$, even $n=2m$ and odd $n=2m+1$.

For even $n=2m$ we have

$$ x^n = x^{2m} = (x^m)^2 $$

For odd $n=2m+1$ we have

$$ x^n = x^{2m+1} = (x^m)^2 \times (a^2 + b^2 + c^2 + d^2) = (ax^m)^2 + (bx^2)^2 + (cx^2)^2 + (cx^2)^2 $$

In summary,

$$ x^n = \begin{cases} (x^m)^2 & \text{even } n=2m \\ \\ (ax^m)^2 + (bx^2)^2 + (cx^2)^2 + (cx^2)^2 & \text{odd } n=2m+1 \end{cases} $$

Exercise (8.2).3

Convert the following integers into sum of four squares:

(a) 217

(b) 819

(c) 2109= 3 × 19 × 37

We'll be using the Sum of Four Squares Identity (8.10) is

$$ \begin{align} (a^2 + b^2 + c^2 + d^2) \times (x^2 + y^2 + z^2 + w^2) & = (ax + by + cz + dw)^2  + (az− bw− cx + dy)^2 \\ \\ & + (ay− bx + cw− dz)^2  + (aw + bz− cy− dx)^2 \end{align} $$

(a) 

$$ 217= 7 \times 31 = (2^2 +1^2 + 1^2 + 1^2) \times (5^2 + 2^2 + 1^2 + 1^2) = 14^2 + 2^2 + 1^2 + 4^2 $$

(b) 

$$ 819 = 3^2 × 7 × 13 =  (2^2 + 1^2 + 1^2 + 1^2) \times (9^2 + 6^2 + 0^2 + 0^2) = 24^2 + 3^2 + 3^2 + 15^2 $$

(c)

$$ 2109 = 57 \times 37 = (7^2 + 2^2 + 2^2 + 0^2) \times (6^2 + 1^2 + 0^2 +0^2) = 44^2 + 12^2 + 5^2 + 2^2 $$

Exercise (8.2).2

Express the following as sum of four squares:

(a) $3072 = 2^{10} \times 3$

(b) $4992 = 2^7 × 3 × 13$

(c) $2015$

(d) $2016$

(e) $2020$

We'll be using the Sum of Four Squares Identity (8.10) is

$$ \begin{align} (a^2 + b^2 + c^2 + d^2) \times (x^2 + y^2 + z^2 + w^2) & = (ax + by + cz + dw)^2  + (az− bw− cx + dy)^2 \\ \\ & + (ay− bx + cw− dz)^2  + (aw + bz− cy− dx)^2 \end{align} $$

(a) 

$$ 3072 = (32)^2 \times 3 = (32)^2 \times (1^2 + 1^2 +1^2 + 0^2)  = 32^2 + 32^2 + 32^2 + 0^2$$

(b)

$$ \begin{align} 4992 & = 2^6 \times 6 \times 13 = 2^6 \times (2^2 + 1^2 + 1^2 + 0^2) \times (3^2 + 2^2 + 0^2 + 0^2) \\ \\ & = 8^2 \times (8^2 + 3^2 + 1^2 + 2^2) = 64^2 + 24^2 + 8^2 + 16^2 \end{align} $$

(c)

$$ 2015 =  65 \times 31 = (8^2 + 1^2 + 0^2 + 0^2) \times (5^2 + 2^2 + 1^2 +1^2) = 42^2 + 7^2 + 11^2 + 9^2 $$

(d)

$$ 2016 = 32 × 63 = (4^2 + 4^2 + 0^2 + 0^2) \times (7^2 + 3^2 +2^2 + 1^2) = 40^2 + 4^2 + 16^2 + 12^2 $$

(e)

$$ 2020 = 20 × 101 = (4^2 + 2^2 + 0^2 +0^2) \times (10^2 + 1^2 + 0^2 + 0^2) = 42^2 + 16^2 + 0^2 + 0^2 $$

Exercise (8.2).1

Convert the following integers into sum of four squares by using the Sum of Four Squares Identity (8.10).

(a) 35 (b) 49 (c) 945 (d) 310 (e) 465 (f) 143

The Sum of Four Squares Identity (8.10) is

$$ \begin{align} (a^2 + b^2 + c^2 + d^2) \times (x^2 + y^2 + z^2 + w^2) & = (ax + by + cz + dw)^2  + (az− bw− cx + dy)^2 \\ \\ & + (ay− bx + cw− dz)^2  + (aw + bz− cy− dx)^2 \end{align} $$

(a)

$$ \begin{align} 35 = 5 \times 7 & = (2^2 + 1^2 + 0^2 + 0^2) \times (2^2 + 1^2 +1^2 +1^2) \\ \\ & =  (4 + 1)^2 + (2 - 1)^2 +(2-2)^2 +(2+1)^2 \\ \\ & = 5^2 + 1^2 + 0^2 + 3^2  \end{align}$$

(b) 

$$  49 = 7 \times 7 = (2^2 + 1^2 +1^2 +1^2) \times (2^2 + 1^2 +1^2 +1^2) = 7^2 + 0^2 + 0^2 + 0^2 $$

(c) 

$$  945 = 9 \times 105 = (3^2 + 0^2 +0^2 +0^2) \times (10^2 + 2^2 +1^2 +0^2)  = 30^2 + 3^2 + 6^2 + 0 $$

(d) 

$$ 310 = 10 \times 31 = (3^2 + 1^2 + 0^2 +0^2) \times (5^2 + 2^2 + 1^2 + 1^2) = 17^2 + 2^2 + 1^2 + 4^2 $$

(e) 

$$ 465 = 15 \times 31 = (3^2 + 2^2 +1^2 + 1^2) \times (5^2 + 2^2 + 1^2 + 1^2) = 21^2 + 2^2 + 4^2 + 2^2 $$

(f)

$$ 143 = 11 \times 13 = (3^2 + 1^2 + 1^2 + 0) \times (3^2 + 2^2 + 0^2 +0^2) = 11^2 + 3^2 + 3^2 + 2^2 $$

Exercise (8.1).25

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$.

Exercise (8.1).24

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$.

We arbitrarily choose a prime $p$ amongst the $p_j$.

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 + b^2 \equiv 0 \pmod p $$

Let $g=\gcd(a,b)$. This means that for some natural numbers we have $a = gx$ and $b = gy$, where $\gcd(x,y)=1$.

And so

$$ m = g^2(x^2 + b^2) = p_1 \times p_2 \times \ldots \times p_r \times N^2$$

This tells us $g^2 \mid N^2$.  And so $\frac{N^2}{g^2}$ is a natural number.

$$ (x^2 + b^2) = p_1 \times p_2 \times \ldots \times p_r \times \frac{N^2}{g^2}$$

It also tells us $p \mid x^2 + y^2$, that is

$$ x^2 + y^2 \equiv 0 \pmod p $$

If $y \equiv 0 \pmod p$ then $x \equiv 0 \pmod p$. That is, for some natural numbers $x', y'$ we have $x=px'$ and $y=py'$. That would mean $\gcd(x,y) \ge p$, contradicting $\gcd(x,y)=1$. And so we can rule out $y\equiv 0 \pmod p$, a fact we'll use below.

The congruence $x^2 + y^2 \equiv 0 \pmod p$ can be written as

$$ x^2 \equiv - y^2 \pmod p  $$

This has solutions if $p \not \mid -y^2$, which we have shown above, and the Legendre symbol $(\frac{-y^2}{p})=1$. Noting that $y=0$ is ruled out, we have

$$ (\frac{-y^2}{p}) = (\frac{-1}{p}) \times \underbrace{(\frac{y^2}{p})}_{=1 \text{ since } y \ne 0}= (\frac{-1}{p}) = 1 $$ 

By Proposition (7.11), $(\frac{-1}{p})= 1$ if an only if $p \equiv 1 \pmod 4$, proving the Theorem (8.7).

Exercise (8.1).23

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:

• If $ac-bd = ac+bd$ then$bd=0$ implying $b=0$ or $d=0$. If $b=0$ then $p=a^2$, which contradicts $p$ is prime. If $d=0$ that would imply $n=c^2$, and this contradicts $n$ being the product of distinct primes. So $ac+bd \ne ac-bd$.
• If $ac-bd = cb-da$ then $c(a-b)=-d(a-b)$, and so $c=-d$, which means $m=2c^2$, contradicting $m$ being a product of distinct primes. So $ac-bd \ne cb-da$.
• If $cb+da=cb-da$ then $da=0$ implying $a=0$ or $d=0$. If $a=0$ then $p=b^2$, which contradicts $p$ is prime. If $d=0$ that would imply $n=c^2$, and this contradicts $n$ being the product of distinct primes. So $cb+da \ne cb-da$.
• If $cb+da = ca+db$ then $c(b-a)=d(b-a)$m and so $c=d$, which means $m=2c^2$, contradicting $m$ being a product of distinct primes. So $cb+da \ne ca+db$.

By assumption $m$ can be written as a sum of squares in $2^{r-1}$ ways, and since $n$ can be written in two ways for the same $m$ and $p$, this means $n$ can be written as a sum of squares in $2^{r-1}\times 2 = 2^r$ ways, 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.

Exercise (8.1).22

(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.

Exercise (8.1).21

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.

Exercise (8.1).20

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.

We have shown both cases lead to the desired conclusion, and so the statement is proven.

Exercise (8.1).19

(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. 

Exercise (8.1).18

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.

Exercise (8.1).17

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 

• swapping $(ac− bd)$ for $(bd-ac)$ which requires swapping $(a^2 + b^2)$ for $(b^2 + a^2)$, and $(c^2 + d^2)$ for $(d^2 + c^2)$.
• swapping $(Ae -  Bf)$ for $(Ae -  Bf)$ which requires swapping $(A^2 +B^2)$ for $(B^2 +A^2)$, and $(e^2 + f^2)$ for $(f^2 + e^2)$,

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} $$