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