Pell’s equation and side and diagonal numbers

1 Side and diagonal numbers

Heath [17, pp. 117–118]:

$$a_1=1,d_1=1.$$

$$a_n=a_{n-1}+d_{n-1},d_n=2a_{n+1}+d_{n+1}.$$

$d_n^2-2a_n^2$ $=4a_{n-1}^2+4a_{n-1}{d}_{n-1}+d_{n-1}^2-2(a_{n-1}^2+2a_{n-1}{d}_{n-1}+d_{n-1}^2)$

$=4a_{n+1}^2+4a_{n+1}{d}_{n+1}+d_{n+1}^2-2a_{n-1}^2-4a_{n-1}{d}_{n-1}-2d_{n-1}^2$

$=2a_{n-1}^2-d_{n-1}^2$

$=-(d_{n-1}^2-2a_{n-1}^2).$

As $d_1^2-2a_1^2=-1$,

$$d_n^2-2a_n^2={(-1)}^n.$$

$$\left(\begin{array}{c}\hfill a_{n+1}\hfill \\ \hfill d_{n+1}\hfill \end{array}\right)=A^n\left(\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right).$$

$A=PD{P}^{-1}$.

$$\left(\begin{array}{c}\hfill a_{n+1}\hfill \\ \hfill d_{n+1}\hfill \end{array}\right)=\left(\begin{array}{c}\hfill \frac{1}{2}{\left(1-\sqrt{2}\right)}^n-\frac{{\left(1-\sqrt{2}\right)}^n}{2\sqrt{2}}+\frac{1}{2}{\left(1+\sqrt{2}\right)}^n+\frac{{\left(1+\sqrt{2}\right)}^n}{2\sqrt{2}}\hfill \\ \hfill \frac{1}{2}{\left(1-\sqrt{2}\right)}^n-\frac{{\left(1-\sqrt{2}\right)}^n}{\sqrt{2}}+\frac{1}{2}{\left(1+\sqrt{2}\right)}^n+\frac{{\left(1+\sqrt{2}\right)}^n}{\sqrt{2}}\hfill \end{array}\right).$$

Thus

$$\left(\begin{array}{c}\hfill a_2\hfill \\ \hfill d_2\hfill \end{array}\right)=\left(\begin{array}{c}\hfill 2\hfill \\ \hfill 3\hfill \end{array}\right),\left(\begin{array}{c}\hfill a_3\hfill \\ \hfill d_3\hfill \end{array}\right)=\left(\begin{array}{c}\hfill 5\hfill \\ \hfill 7\hfill \end{array}\right),\left(\begin{array}{c}\hfill a_4\hfill \\ \hfill d_4\hfill \end{array}\right)=\left(\begin{array}{c}\hfill 12\hfill \\ \hfill 17\hfill \end{array}\right),\left(\begin{array}{c}\hfill a_5\hfill \\ \hfill d_5\hfill \end{array}\right)=\left(\begin{array}{c}\hfill 29\hfill \\ \hfill 41\hfill \end{array}\right).$$

2 Diophantus

If $x^2-A{y}^2=1$ and $y=m(x+1)$ for rational $m$, then $y^2=m^2(x^2+2x+1)$, then $x^2-A{m}^2(x^2+2x+1)=1$, then $(A{m}^2-1)x^2+2A{m}^{2}x+A{m}^2+1=0$. Write $(x+1)(px+q)=(A{m}^2-1)x^2+2A{m}^{2}x+A{m}^2+1$. Then $p{x}^2+(p+q)x+q=(A{m}^2-1)x^2+2A{m}^{2}x+A{m}^2+1$. Then $p=A{m}^2-1$, $q=A{m}^2+1$, and so $p+q=A{m}^2-1+A{m}^2+1=2A{m}^2$. Thus if $x\ne -1$ then $px+q=0$ and hence $(A{m}^2-1)x+A{m}^2+1=0$. Hence $(A{m}^2-1)x=-(A{m}^2+1)$ and so $x=-\frac{A{m}^2+1}{A{m}^2-1}$. Thus

$$y=m(x+1)=m\left(-\frac{A{m}^2+1}{A{m}^2-1}+1\right)\frac{m}{A{m}^2-1}(-A{m}^2-1+A{m}^2-1)=\frac{-2m}{A{m}^2-1}.$$

Therefore for rational $m$,

$$x=-\frac{A{m}^2+1}{A{m}^2-1},y=\frac{-2m}{A{m}^2-1}$$

satisfy $x^2-A{y}^2=1$. cf. Heath [17, pp. 68–69], Nesselmann [24, p. 331].

Diophantus V.11: $30x^2+1=y^2$. Say $y=5x+1$. $y^2=25x^2+10x+1$. Then $5x^2-10x=0$, so $x=0$ or $5x-10=0$, i.e. $x=0$ or $x=2$. Hence $x=0,y=1$ and $x=2,y=11$ satisfy $30x^2+1=y^2$.

Diophantus V.14 [17, pp. 211–212]. $34y^2+1=x^2$. Say $x=6y-1$. $x^2=36y^2-12y+1$. Then $2y^2-12y=0$, i.e. $y(y-6)=0$ so $y=0$ or $y=6$. Then $x=-1,y=0$ and $x=35,y=6$ satisfy $34y^2+1=x^2$.

3 Fermat

Fermat, February 1657 [31, p. 29]:

Given any number not a square, then there are an infinite number of squares which, when multiplied by the given number, make a square when unity is added.
Example. Given 3, a nonsquare number; this number multiplied by the square number 1, and 1 being added, produces 4, which is a square.
Moreover, the same 3 multiplied by the square 16, with 1 added makes 49, which is a square.
And instead of 1 and 16, an infinite number of squares may be found showing the same property; I demand, however, a general rule, any number being given which is not a square.
It is sought, for example, to find a square which when multiplied into 149, 109, 433, etc., becomes a square when unity is added.

4 Wallis

Wallis [1, p. 546].

Stedall [29]

5 Brouncker

Weil [32, pp. 92–99].

6 Ozanam

Ozanam [25, pp. 503–516], Liv. III, Quest. XXVI.

7 Continued fractions

Let

$$[a_0,a_1]=a_0+\frac{1}{a_1}$$

and

$$[a_0,\mathrm{\dots },a_{n-1},a_n]=[a_0,\mathrm{\dots },a_{n-2},a_{n-1}+\frac{1}{a_n}].$$

Then for ,

$$[a_0,\mathrm{\dots },a_n]=[a_0,\mathrm{\dots },a_{m-1},[a_m,\mathrm{\dots },a_n]].$$

Define

$$p_0=a_0,q_0=1,p_1=a_1{a}_0+1,q_1=a_1$$

and for $n\ge 2$,

$$p_n=a_n{p}_{n-1}+p_{n-2},q_n=a_n{q}_{n-1}+q_{n-2}.$$

Hardy and Wright [13, p. 130, Theorem 149]. For $n\ge 0$,

$$[a_0,\mathrm{\dots },a_n]=\frac{p_n}{q_n}.$$

For $n\ge 1$,

$$p_n{q}_{n-1}-p_{n-1}{q}_n={(-1)}^{n-1}.$$

For $n\ge 2$,

$$p_n{q}_{n-2}-p_{n-2}{q}_n={(-1)}^n{a}_n.$$

For $n\ge 0$ let

$$a_n^{\prime }=[a_n,a_{n+1},\mathrm{\dots }].$$

For $x=[a_0,a_1,\mathrm{\dots }]$,

$$x=\frac{a_n^{\prime }{p}_{n-1}+p_{n-2}}{a_n^{\prime }{q}_{n-1}+q_{n-2}},n\ge 2.$$

Hardy and Wright [13, p. 144, Theorem 176]. A continued fraction $[a_0,a_1,\mathrm{\dots }]$ is said to be periodic if there is some $L\ge 0$ and some $k\ge 1$ such that $a_{l+k}=a_l$ for all $l\ge L$.

Theorem 1.

If $x=[a_0,a_1,\mathrm{\dots }]$ is a periodic continued fraction, then $x$ is a quadratic surd.

Proof.

Let

$$\overline{a_L,\mathrm{\dots },a_{L+k-1}}=[a_L,a_{L+1},\mathrm{\dots }]=a_L^{\prime }.$$

Thus

$[a_0,\mathrm{\dots },a_{L-1},a_L,a_{L+1},\mathrm{\dots }]$ $=[a_0,\mathrm{\dots },a_{L-1},a_L^{\prime }]$

$=[a_0,\mathrm{\dots },a_{L-1},\overline{a_L,\mathrm{\dots },a_{L+k-1}}].$

As $a_{L+k}=a_L,a_{L+k+1}=a_{L+1},\mathrm{\dots }$,

$a_L^{\prime }$ $=[a_L,a_{L+1},\mathrm{\dots }]$

$=[a_L,a_{L+1},\mathrm{\dots },a_{L+k-1},a_L,a_{L+1},\mathrm{\dots }]$

$=[a_L,a_{L+1},\mathrm{\dots },a_{L+k-1},a_L^{\prime }].$

Let

$$\frac{p^{\prime }}{q^{\prime }}=[a_L,a_{L+1},\mathrm{\dots },a_{L+k-1}],\frac{p^{\prime \prime }}{q^{\prime \prime }}=[a_L,a_{L+1},\mathrm{\dots },a_{L+k-2}].$$

For $t=[a_L,a_{L+1},\mathrm{\dots },a_{L+k-1},a_L^{\prime }]$,

$$t=\frac{a_L^{\prime }{p}^{\prime }+p^{\prime \prime }}{a_L^{\prime }{q}^{\prime }+q^{\prime \prime }}=\frac{p^{\prime }t+p^{\prime \prime }}{q^{\prime }t+q^{\prime \prime }}.$$

Hence $q^{\prime }{t}^2+q^{\prime \prime }t=p^{\prime }t+p^{\prime \prime }$, so $q^{\prime }{t}^2+(q^{\prime \prime }-p^{\prime })t-p^{\prime \prime }=0$. For $x=[a_0,a_1,\mathrm{\dots }]$,

$$x=\frac{a_L^{\prime }{p}_{L-1}+p_{L-2}}{a_L^{\prime }{q}_{L-1}+q_{L-2}}.$$

Then

$$a_L^{\prime }=\frac{p_{L-2}-q_{L-2}x}{q_{L-1}x-p_{L-1}}.$$

Thus, with $t=a_L^{\prime }$,

$$q^{\prime }{\left(\frac{p_{L-2}-q_{L-2}x}{q_{L-1}x-p_{L-1}}\right)}^2+(q^{\prime \prime }-p^{\prime })\frac{p_{L-2}-q_{L-2}x}{q_{L-1}x-p_{L-1}}-p^{\prime \prime }=0.$$

Then

$$q^{\prime }{(p_{L-2}-q_{L-2}x)}^2+(q^{\prime \prime }-p^{\prime })(p_{L-2}-q_{L-2}x)(q_{L-1}x-p_{L-1})-p^{\prime \prime }{(q_{L-1}x-p_{L-1})}^2=0.$$

Therefore there are integers $a,b,c$ such that

$$a{x}^2+bx+c=0.$$

This means that $x$ is a quadratic surd, as $x$ is irrational. ∎

Example. Say $x=[3,2,7,4,\overline{5,1,12}]$. $L=4,k=3$.

$$\frac{p^{\prime }}{q^{\prime }}=[5,1,12]=\frac{77}{13},\frac{p^{\prime \prime }}{q^{\prime \prime }}=[5,1]=\frac{6}{1}.$$

$$\frac{p_{L-1}}{q_{L-1}}=\frac{p_3}{q_3}=[3,2,7,4]=\frac{215}{62},\frac{p_{L-2}}{q_{L-2}}=\frac{p_2}{q_2}=[3,2,7]=\frac{52}{15}.$$

Then

$q^{\prime }{(p_{L-2}-q_{L-2}x)}^2+(q^{\prime \prime }-p^{\prime })(p_{L-2}-q_{L-2}x)(q_{L-1}x-p_{L-1})-p^{\prime \prime }{(q_{L-1}x-p_{L-1})}^2$

$=$ $13{(52-15x)}^2+(1-77)(52-15x)(62x-215)-6{(62x-215)}^2$

$=$ $50541x^2-350444x+607482.$

Hence $x=[3,2,7,4,\overline{5,1,12}]$ satisfies

$$50541x^2-350444x+607482=0.$$

In fact,

$$x=\frac{175222+\sqrt{1522}}{50541}.$$

Hardy and Wright [13, p. 144, Theorem 177].

Theorem 2.

If $x$ is a quadratic surd, then the continued fraction of $x$ is periodic.

Example. Say $x^2=218$. ${14}^2=196$.

$$\sqrt{218}=14+\sqrt{218}-14=14+\frac{1}{{\displaystyle \frac{1}{\sqrt{218}-14}}}.$$

$$(\sqrt{218}-14)(\sqrt{218}+14)=218-196=22,\frac{1}{\sqrt{218}-14}=\frac{\sqrt{218}+14}{22}.$$

We do not need to compute the decimal expansion of $\sqrt{218}$; we merely have to calculate $\lfloor \frac{\sqrt{218}+14}{22}\rfloor$. Using ,

$$\frac{1}{\sqrt{218}-14}=1+\frac{\sqrt{218}+14}{22}-1=1+\frac{\sqrt{218}-8}{22}.$$

Then

$$\sqrt{218}=14+\frac{1}{1+{\displaystyle \frac{\sqrt{218}-8}{22}}}=14+\frac{1}{1+{\displaystyle \frac{1}{{\displaystyle \frac{22}{\sqrt{218}-8}}}}}$$

$$(\sqrt{218}-8)(\sqrt{218}+8)=218-64=154,\frac{1}{\sqrt{218}-8}=\frac{\sqrt{218}+8}{154}.$$

Then

$$\frac{22}{\sqrt{218}-8}=\frac{22\sqrt{218}+176}{154}.$$

Using that ,

$$\frac{22}{\sqrt{218}-8}=3+\frac{22\sqrt{218}+176}{154}-3=3+\frac{22\sqrt{218}-286}{154}.$$

Then

$$\sqrt{218}=14+\frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{22\sqrt{218}-286}{154}}}}}=14+\frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{{\displaystyle \frac{154}{22\sqrt{218}-286}}}}}}}.$$

$$(22\sqrt{218}-286)(22\sqrt{218}+286)={22}^2\cdot 218-{286}^2=23716,$$

$$\frac{1}{22\sqrt{218}-286}=\frac{22\sqrt{218}+286}{23716}.$$

$$\frac{154}{22\sqrt{218}-286}=\frac{3388\sqrt{218}+44044}{23716}.$$

Using ,

$$\frac{154}{22\sqrt{218}-286}=3+\frac{3388\sqrt{218}+44044}{23716}-3=3+\frac{3388\sqrt{218}-27104}{23716}.$$

Then

$$\sqrt{218}=14+\frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{3+{\displaystyle \frac{3388\sqrt{218}-27104}{23716}}}}}}}=14+\frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{{\displaystyle \frac{23716}{3388\sqrt{218}-27104}}}}}}}}}.$$

$$(3388\sqrt{218}-27104)(3388\sqrt{218}+27104)={3388}^2\cdot 218-{27104}^2=1767695776,$$

$$\frac{1}{3388\sqrt{218}-27104}=\frac{3388\sqrt{218}+27104}{1767695776}.$$

$$\frac{23716}{3388\sqrt{218}-27104}=23716\cdot \frac{3388\sqrt{218}+27104}{1767695776}.$$

Using ,

${\displaystyle \frac{23716}{3388\sqrt{218}-27104}}$ $=1+23716\cdot {\displaystyle \frac{3388\sqrt{218}+27104}{1767695776}}-1$

$=1+{\displaystyle \frac{80349808\sqrt{218}-1124897312}{1767695776}}.$

Then

$\sqrt{218}$ $=14+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{1+{\displaystyle \frac{80349808\sqrt{218}-1124897312}{1767695776}}}}}}}}}}$

$=14+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{{\displaystyle \frac{1767695776}{80349808\sqrt{218}-1124897312}}}}}}}}}}}}.$

$$(80349808\sqrt{218}-1124897312)(80349808\sqrt{218}+1124897312)=142034016204011008.$$

$$\frac{1767695776}{80349808\sqrt{218}-1124897312}=1767695776\cdot \frac{80349808\sqrt{218}+1124897312}{142034016204011008}.$$

Using , the floor of the above quantity is 28. Hence

${\displaystyle \frac{1767695776}{80349808\sqrt{218}-1124897312}}$ $=28+{\displaystyle \frac{142034016204011008\sqrt{218}-1988476226856154112}{142034016204011008}}$

$=28+\sqrt{218}-14.$

Then

$\sqrt{218}$ $=14+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{28+\sqrt{218}-14}}}}}}}}}}$

Thus for $x=\sqrt{218}$,

$$x-14=\frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{28+x-14}}}}}}}}}.$$

Thus for $t=x-14$,

$$t=\frac{1}{1+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{3+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{28+t}}}}}}}}}.$$

Therefore $t=[0,\overline{1,3,3,1,28}]$. Hence $x=14+t=[14,\overline{1,3,3,1,28}]$:

$$\sqrt{218}=[14,\overline{1,3,3,1,28}].$$

8 Euler

Euler, Algebra [10], Part II, Chapter VII.

9 Lagrange

Konen [20, pp. 75–77].

10 Chakravala

Hankel [12, pp. 200–203]

Strachey [30, pp. 36–53]. Dickson [5, pp. 349–350].

Colebrooke [3, pp. 170–184]

Colebrooke [3, pp. 363–372]

Datta and Singh [4, II, pp. 93–99]

Datta and Singh [4, II, pp. 146–161]

Datta and Singh [4, II, pp. 161–172]

Suppose that $p_n,q_n$ are relatively prime and

$$A{q}_n^2+s_n=p_n^2.$$

If $d$ is a common factor of $q_n$ and $s_n$ then $d\mid p_n^2$, so $d$ is a common factor of $p_n^2$ and $q_n^2$, which implies that $p_n$ and $q_n$ have a common factor, a contradiction. Therefore $q_n$ and $s_n$ are relatively prime. Because $q_n$ and $s_n$ are relatively prime, by the Kuttaka algorithm there are some ${\rho }_n,{\rho }_n^{\prime }$ satisfying $-q_n{\rho }_n+s_n{\rho }_n^{\prime }=p_n$. For $r_n={\rho }_n+k_n{s}_n$, $r_n^{\prime }={\rho }_n^{\prime }+k_n{q}_n$,

$-q_n{r}_n+s_n{r}_n^{\prime }$ $=-q_n({\rho }_n+k_n{s}_n)+s_n({\rho }_n^{\prime }+k_n{q}_n)$

$=-q_n{\rho }_n-k_n{q}_n{s}_n+s_n{\rho }_n^{\prime }+k_n{q}_n{s}_n$

$=-q_n{\rho }_n+s_n{\rho }_n^{\prime }$

$=p_n.$

Take . $r_n^{\prime }=\frac{p_n+q_n{r}_n}{s_n}$. Let

$$q_{n+1}=r_n^{\prime },p_{n+1}=\frac{p_n{q}_{n+1}-1}{q_n},s_{n+1}=p_{n+1}^2-A{q}_{n+1}^2.$$

Example. $69y^2+1=x^2$. $A=69$.

$A{q}_0^2+s_0=p_0^2$: $p_0=8,q_0=1,s_0=-5$.

$p_0+q_0{\rho }_0={\rho }_0^{\prime }{s}_0$ is equivalent to $8+{\rho }_0=-5{\rho }_0^{\prime }$. It is satisfied by ${\rho }_0=-8,{\rho }_0^{\prime }=0$. Take $r_0=-8-5k_0=7$. $r_0^{\prime }=\frac{p_0+q_0{r}_0}{s_0}=\frac{8+1\cdot 7}{-5}=-3$.

$q_1=-3$.

$$p_1=\frac{p_0{q}_1-1}{q_0}=\frac{8\cdot -3-1}{1}=-25.$$

$$s_1=p_1^2-A{q}_1^2=4.$$

$p_1+q_1{\rho }_1={\rho }_1^{\prime }{s}_1$ is equivalent to $-25-3{\rho }_1=4{\rho }_1^{\prime }$. This is satisfied by ${\rho }_1=1,{\rho }_1^{\prime }=-7$. Take $r_1=1+4k_1=5$. Then $r_1^{\prime }=\frac{p_1+q_1{r}_1}{s_1}=\frac{-25-3\cdot 5}{4}=-10$.

$q_2=-10$.

$$p_2=\frac{p_1{q}_2-1}{q_1}=\frac{-25\cdot -10-1}{-3}=-83.$$

$$s_2=p_2^2-A{q}_2^2=-11.$$

$p_2+q_2{\rho }_2={\rho }_2^{\prime }{s}_2$ is equivalent to $-83-10{\rho }_2=-11{\rho }_2^{\prime }$. This is satisfied by ${\rho }_2=6,{\rho }_2^{\prime }=13$. Take $r_2=6-11k_2=6$. Then $r_2^{\prime }=\frac{p_2+q_2{r}_2}{s_2}=\frac{-83-10\cdot 6}{-11}=13$.

$q_3=13$.

$$p_3=\frac{p_2{q}_3-1}{q_2}=\frac{-83\cdot 13-1}{-10}=108.$$

$$s_3=p_3^2-A{q}_3^2=3.$$

$p_3+q_3{\rho }_3={\rho }_3^{\prime }{s}_3$ is equivalent to $108+13{\rho }_3=3{\rho }_3^{\prime }$. This is satisfied by ${\rho }_3=0,{\rho }_3^{\prime }=36$. Take $r_3=36+3k_3=6$. Then $r_3^{\prime }=\frac{p_3+q_3{r}_3}{s_3}=\frac{108+13\cdot 6}{3}=62$.

$q_4=62$.

$$p_4=\frac{p_3{q}_4-1}{q_3}=\frac{108\cdot 62-1}{13}=515.$$

$$s_4=p_4^2-A{q}_4^2=-11.$$

$p_4+q_4{\rho }_4={\rho }_4^{\prime }{s}_4$ is equivalent to $515+62{\rho }_4=-11{\rho }_4^{\prime }$. This is satisfied by ${\rho }_4=5,{\rho }_4^{\prime }=-75$. Take $r_4=5-11k_4=5$. Then $r_4^{\prime }=\frac{p_4+q_4{r}_4}{s_4}=\frac{515+62\cdot 5}{-11}=-75$.

$q_5=-75$.

$$p_5=\frac{p_4{q}_5-1}{q_4}=\frac{515\cdot -75-1}{62}=-623.$$

$$s_5=p_5^2-A{q}_5^2=4.$$

$p_5+q_5{\rho }_5={\rho }_5^{\prime }{s}_5$ is equivalent to $-623-75{\rho }_5=4{\rho }_5^{\prime }$. This is satisfied by ${\rho }_5=3,{\rho }_5^{\prime }=-212$. Take $r_5=3+4k_5=7$. Then $r_5^{\prime }=\frac{p_5+q_5{r}_5}{s_5}=\frac{-623-75\cdot 7}{4}=-287$.

$q_6=-287$.

$$p_6=\frac{p_5{q}_6-1}{q_5}=\frac{-623\cdot -287-1}{-75}=-2384.$$

$$s_6=p_6^2-A{q}_6^2=-5.$$

$p_6+q_6{\rho }_6={\rho }_6^{\prime }{s}_6$ is equivalent to $-2384-287{\rho }_6=-5{\rho }_6^{\prime }$. This is satisfied by ${\rho }_6=3,{\rho }_6^{\prime }=649$. Take $r_6=3-5k=8$. Then $r_6^{\prime }=\frac{p_6+q_6{r}_6}{s_6}=\frac{-2384-287\cdot 8}{-5}=936$.

$q_7=936$.

$$p_7=\frac{p_6{q}_7-1}{q_6}=\frac{-2384\cdot 936-1}{-287}=7775.$$

$$s_7=p_7^2-A{q}_7^2=1.$$

Therefore

$${7775}^2-69\cdot {936}^2=1.$$

Thus $\sqrt{69}\sim \frac{7775}{936}$.

Example. $91y^2+1=x^2$. $A=91$.

$A{q}_0^2+s_0=p_0^2$: $p_0=10$, $q_0=1$, $s_0=9$.

$p_0+q_0{\rho }_0={\rho }_0^{\prime }{s}_0$ is equivalent to $10+{\rho }_0=9{\rho }_0^{\prime }$. This is satisfied by ${\rho }_0=-10$, ${\rho }_0^{\prime }=0$. Take $r_0=-10+9k_0=8$. Then $r_0^{\prime }=\frac{p_0+q_0{r}_0}{s_0}=\frac{10+1\cdot 8}{9}=2$.

$q_1=2$.

$$p_1=\frac{p_0{q}_1-1}{q_0}=\frac{10\cdot 2-1}{1}=19.$$

$$s_1=p_1^2-A{q}_1^2=-3.$$

$p_1+q_1{\rho }_1={\rho }_1^{\prime }{s}_1$ is equivalent with $19+2{\rho }_1=-3{\rho }_1^{\prime }$. This is satisfied by ${\rho }_1=1,{\rho }_1^{\prime }=-7$. Take $r_1=1-3k_1=7$. Then $r_1^{\prime }=\frac{p_1+q_1{r}_1}{s_1}=\frac{19+2\cdot 7}{-3}=-11$.

$q_2=-11$.

$$p_2=\frac{p_1{q}_2-1}{q_1}=\frac{19\cdot -11-1}{2}=-105.$$

$$s_2=p_2^2-A{q}_2^2=14.$$

$p_2+q_2{\rho }_2={\rho }_2^{\prime }{s}_2$ is equivalent with $-105-11{\rho }_2=14{\rho }_2^{\prime }$. This is satisfied by ${\rho }_2=7,{\rho }_2^{\prime }=-13$. Take $r_2=7,r_2^{\prime }=-13$.

$q_3=-13$.

$$p_3=\frac{p_2{q}_3-1}{q_2}=\frac{-105\cdot -13-1}{-11}=-124.$$

$$s_3=p_3^2-A{q}_3^2=-3.$$

$p_3+q_3{\rho }_3={\rho }_3^{\prime }{s}_3$ is equivalent with $-124-13{\rho }_3=-3{\rho }_3^{\prime }$. This is satisfied by ${\rho }_3=2,{\rho }_3^{\prime }=50$. Take $r_3=2-3k_3=8$. Then $r_3^{\prime }=\frac{p_3+q_3{r}_3}{s_3}=\frac{-124-13\cdot 8}{-3}=76$.

$q_4=76$.

$$p_4=\frac{p_3{q}_4-1}{q_3}=\frac{-124\cdot 76-1}{-13}=725.$$

$$s_4=p_4^2-A{q}_4^2=9.$$

$p_4+q_4{\rho }_4={\rho }_4^{\prime }{s}_4$ is equivalent with $725+76{\rho }_4=9{\rho }_4^{\prime }$. This is satisfied by ${\rho }_4=1,{\rho }_4^{\prime }=89$. Take $r_4=1$, $r_4^{\prime }=89$.

$q_5=89$.

$$p_5=\frac{p_4{q}_5-1}{q_4}=\frac{725\cdot 89-1}{76}=849.$$

$$s_5=p_5^2-A{q}_5^2=-10.$$

$p_5+q_5{\rho }_5={\rho }_5^{\prime }{s}_5$ is equivalent with $849+89{\rho }_5=-10{\rho }_5^{\prime }$. This is satisfied by ${\rho }_5=9,{\rho }_5^{\prime }=-165$. Take $r_5=9,r_5^{\prime }=-165$.

$q_6=-165$.

$$p_6=\frac{p_5{q}_6-1}{q_5}=\frac{849\cdot -165-1}{89}=-1574.$$

$$s_6=p_6^2-A{q}_6^2=1.$$

Therefore

$${1574}^2-91\cdot {165}^2=1.$$

Thus $\sqrt{91}\sim \frac{1574}{165}$.

Example. $109y^2+1=x^2$. $A=109$.

$A{y}_0^2+s_0=x_0^2$: $x_0=10$, $y_0=1$, $s_0=-9$.

$x_0+y_0{\rho }_0=s_0{\rho }_0^{\prime }$ is equivalent to $10+{\rho }_0=-9{\rho }_0^{\prime }$. This is satisfied by ${\rho }_0=-10$, ${\rho }_0^{\prime }=0$. Take $r_0=-10+9k_0=8$. Then $r_0^{\prime }=\frac{x_0+y_0{r}_0}{s_0}=\frac{10+1\cdot 8}{-9}=-2$.

$y_1=-2$.

$$x_1=\frac{x_0{y}_1-1}{y_0}=\frac{10\cdot -2-1}{1}=-21.$$

$$s_1=x_1^2-A{y}_1^2=5.$$

$x_1+y_1{\rho }_1={\rho }_1^{\prime }{s}_1$ is equivalent with $-21-2{\rho }_1=5{\rho }_1^{\prime }$. This is satisfied by ${\rho }_1=2,{\rho }_1^{\prime }=-5$. Take $r_1=2+5k_1=7$. Then $r_1^{\prime }=\frac{x_1+y_1{r}_1}{s_1}=\frac{-21-2\cdot 7}{5}=-7$.

$y_2=-7$.

$$x_2=\frac{x_1{y}_2-1}{y_1}=\frac{-21\cdot -7-1}{-2}=-73.$$

$$s_2=x_2^2-A{y}_2^2=-12.$$

$x_2+y_2{\rho }_2={\rho }_2^{\prime }{s}_2$ is equivalent with $-73-7{\rho }_2=-12{\rho }_1^{\prime }$. This is satisfied by ${\rho }_2=5,{\rho }_2^{\prime }=9$. Take $r_2=5,r_2^{\prime }=9$.

$y_3=9$.

$$x_3=\frac{x_2{y}_3-1}{y_2}=\frac{-73\cdot 9-1}{-7}=94.$$

$$s_3=x_3^2-A{y}_3^2=7.$$

$x_3+y_3{\rho }_3={\rho }_3^{\prime }{s}_3$ is equivalent with $94+9{\rho }_3=7{\rho }_3^{\prime }$. This is satisfied by ${\rho }_3=2,{\rho }_3^{\prime }=16$. Take $r_3=2+7k_3=9$. Then $r_3^{\prime }=\frac{x_3+y_3{r}_3}{s_3}=\frac{94+9\cdot 9}{7}=25$.

$y_4=25$.

$$x_4=\frac{x_3{y}_4-1}{y_3}=\frac{94\cdot 25-1}{9}=261.$$

$$s_4=x_4^2-A{y}_4^2=-4.$$

$x_4+y_4{\rho }_4={\rho }_4^{\prime }{s}_4$ is equivalent with $261+25{\rho }_4=-4{\rho }_4^{\prime }$. This is satisfied by ${\rho }_4=3,{\rho }_4^{\prime }=-84$. Take $r_4=3-4k_4=7$. Then $r_4^{\prime }=\frac{x_4+y_4{r}_4}{s_4}=\frac{261+25\cdot 7}{-4}=-109$.

$y_5=-109$.

$$x_5=\frac{x_4{y}_5-1}{y_4}=\frac{261\cdot -109-1}{25}=-1138.$$

$$s_5=x_5^2-A{y}_5^2=15.$$

$x_5+y_5{\rho }_5={\rho }_5^{\prime }{s}_5$ is equivalent with $-1138-109{\rho }_5=15{\rho }_5^{\prime }$. This is satisfied by ${\rho }_5=8,{\rho }_5^{\prime }=-134$. Take $r_5=8,r_5^{\prime }=-134$.

$y_6=-134$.

$$x_6=\frac{x_5{y}_6-1}{y_5}=\frac{-1138\cdot -134-1}{-109}=-1399.$$

$$s_6=x_6^2-A{y}_6^2=-3.$$

$x_6+y_6{\rho }_6={\rho }_6^{\prime }{s}_6$ is equivalent with $-1399-134{\rho }_6=-3{\rho }_6^{\prime }$. This is satisfied by ${\rho }_6=1,{\rho }_6^{\prime }=511$. Take $r_6=1-3k_6=10$. Then $r_6^{\prime }=\frac{x_6+y_6{r}_6}{s_6}=\frac{-1399-134\cdot 10}{-3}=913$.

$y_7=913$.

$$x_7=\frac{x_6{y}_7-1}{y_6}=\frac{-1399\cdot 913-1}{-134}=9532.$$

$$s_7=x_7^2-A{y}_7^2=3.$$

$x_7+y_7{\rho }_7={\rho }_7^{\prime }{s}_7$ is equivalent with $9532+913{\rho }_7=3{\rho }_7^{\prime }$. This is satisfied by ${\rho }_7=2,{\rho }_7^{\prime }=3786$. Take $r_7=2+3k_7=8$. Then $r_7^{\prime }=\frac{x_7+y_7{r}_7}{s_7}=\frac{9532+913\cdot 8}{3}=5612$.

$y_8=5612$.

$$x_8=\frac{x_7{y}_8-1}{y_7}=\frac{9532\cdot 5612-1}{913}=58591.$$

$$s_8=x_8^2-A{y}_8^2=-15.$$

$x_8+y_8{\rho }_8={\rho }_8^{\prime }{s}_8$ is equivalent with $58591+5612{\rho }_8=-15{\rho }_8^{\prime }$. This is satisfied by ${\rho }_8=7,{\rho }_7^{\prime }=-6525$. Take $r_8=7,r_8^{\prime }=-6525$.

$y_9=-6525$.

$$x_9=\frac{x_8{y}_9-1}{y_8}=\frac{58591\cdot -6525-1}{5612}=-68123.$$

$$s_9=x_9^2-A{y}_9^2=4.$$

$x_9+y_9{\rho }_9={\rho }_9^{\prime }{s}_9$ is equivalent with $-68123-6525{\rho }_9=4{\rho }_9^{\prime }$. This is satisfied by ${\rho }_9=1,{\rho }_9^{\prime }=-18662$. Take $r_9=1+4k_9=9$. Then $r_9^{\prime }=\frac{x_9+y_9{r}_9}{s_9}=\frac{-68123-6525\cdot 9}{4}=-31712$.

$y_{10}=-31712$.

$$x_{10}=\frac{x_9{y}_{10}-1}{y_9}=\frac{-68123\cdot (-31712)-1}{-6525}=-331083.$$

$$s_{10}=x_{10}^2-A{y}_{10}^2=-7.$$

$x_{10}+y_{10}{\rho }_{10}={\rho }_{10}^{\prime }{s}_{10}$ is equivalent with $-331083-31712{\rho }_{10}=-7{\rho }_{10}^{\prime }$. This is satisfied by ${\rho }_{10}=5,{\rho }_{10}^{\prime }=69949$. Take $r_{10}=5,r_{10}^{\prime }=69949$.

$y_{11}=69949$.

$$x_{11}=\frac{x_{10}{y}_{11}-1}{y_{10}}=\frac{-331083\cdot 69949-1}{-31712}=730289.$$

$$s_{11}=x_{11}^2-A{y}_{11}^2=12.$$

$x_{11}+y_{11}{\rho }_{11}={\rho }_{11}^{\prime }{s}_{11}$ is equivalent with $730289+69949{\rho }_{11}=12{\rho }_{11}^{\prime }$. This is satisfied by ${\rho }_{11}=7,{\rho }_{11}^{\prime }=101661$. Take $r_{11}=5,r_{10}^{\prime }=101661$.

$y_{12}=101661$.

$$x_{12}=\frac{x_{11}{y}_{12}-1}{y_{11}}=\frac{730289\cdot 101661-1}{69949}=1061372.$$

$$s_{12}=x_{12}^2-A{y}_{12}^2=-5.$$

$x_{12}+y_{12}{\rho }_{12}={\rho }_{12}^{\prime }{s}_{12}$ is equivalent with $1061372+101661{\rho }_{12}=-5{\rho }_{12}^{\prime }$. This is satisfied by ${\rho }_{12}=3,{\rho }_{12}^{\prime }=-273271$. Take $r_{12}=3-5k_{12}=8$. Then $r_{12}^{\prime }=\frac{x_{12}+y_{12}{r}_{12}}{s_{12}}=\frac{1061372+101661\cdot 8}{-5}=-374932$.

$y_{13}=-374932$.

$$x_{13}=\frac{x_{12}{y}_{13}-1}{y_{12}}=\frac{1061372\cdot (-374932)-1}{101661}=-3914405.$$

$$s_{13}=x_{13}^2-A{y}_{13}^2=9.$$

$x_{13}+y_{13}{\rho }_{13}={\rho }_{13}^{\prime }{s}_{13}$ is equivalent with $-3914405-374932{\rho }_{13}=9{\rho }_{13}^{\prime }$. This is satisfied by ${\rho }_{13}=1,{\rho }_{13}^{\prime }=-476593$. Take $r_{13}=1+9k_{13}=10$. Then $r_{13}^{\prime }=\frac{x_{13}+y_{13}{r}_{13}}{s_{13}}=\frac{-3914405-374932\cdot 10}{9}=-851525$.

$y_{14}=-851525$.

$$x_{14}=\frac{x_{13}{y}_{14}-1}{y_{13}}=\frac{-3914405\cdot (-851525)-1}{-374932}=-8890182.$$

$$s_{14}=x_{14}^2-A{y}_{14}^2=-1.$$

$x_{14}+y_{14}{\rho }_{14}={\rho }_{14}^{\prime }{s}_{14}$ is equivalent with $-8890182-851525{\rho }_{14}=-{\rho }_{14}^{\prime }$. This is satisfied by ${\rho }_{14}=0,{\rho }_{14}^{\prime }=8890182$. Take $r_{14}=-k_{14}=10$. Then $r_{14}^{\prime }=\frac{x_{14}+y_{14}{r}_{14}}{s_{14}}=\frac{-8890182-851525\cdot 10}{-1}=17405432$.

$y_{15}=17405432$.

$$x_{15}=\frac{x_{14}{y}_{15}-1}{y_{14}}=\frac{-8890182\cdot 17405432-1}{-851525}=181718045.$$

$$s_{15}=x_{15}^2-A{y}_{15}^2=9.$$

$r_{15}=8,r_{15}^{\prime }=35662389$.

$y_{16}=35662389$.

$$x_{16}=\frac{x_{15}{y}_{16}-1}{y_{15}}=\frac{35662389\cdot 35662389-1}{17405432}=372326272.$$

$$s_{16}=x_{16}^2-A{y}_{16}^2=-5.$$

${\rho }_{16}=2,{\rho }_2^{\prime }=-88730210$. $r_{16}=2-5k_{16}=7$. Then $r_{16}^{\prime }=-124392599$.

$y_{17}=-124392599$.

$$x_{17}=-1298696861.$$

$$s_{17}=12.$$

$r_{18}=5,r_{18}^{\prime }=-160054988$.

$y_{18}=-160054988$.

$$x_{18}=-1671023133.$$

$$s_{18}=-7.$$

${\rho }_{19}=2,{\rho }_{19}^{\prime }=284447587$. Take $r_{19}=2-7k_{19}=9$. Then $r_{19}^{\prime }=444502575$.

$y_{19}=444502575$.

$$x_{19}=4640743127.$$

$$s_{19}=4.$$

${\rho }_{20}=3,{\rho }_{20}^{\prime }=1493562713$. Take $r_{20}=3+4k_{20}=7$. Then $r_{20}^{\prime }=1938065288$.

$y_{20}=1938065288$.

$$x_{20}=20233995641.$$

$$s_{20}=-15.$$

$r_{21}=8,r_{21}^{\prime }=-2382567863$.

$y_{21}=-2382567863$.

$$x_{21}=-24874738768.$$

$$s_{21}=3.$$

${\rho }_{22}=1,{\rho }_{22}^{\prime }=-9085768877$. Take $r_{22}=1+3k_{22}=10$. Then $r_{22}^{\prime }=-16233472466$.

$y_{22}=-16233472466$.

$$x_{22}=.-169482428249.$$

$$s_{22}=-3.$$

${\rho }_{23}=2,{\rho }_{23}^{\prime }=67316457727$. Take $r_{23}=2-3k_{23}=8$. Then $r_{23}^{\prime }=99783402659$.

$y_{23}=99783402659$.

$$x_{23}=1041769308262.$$

$$s_{23}=15.$$

$r_{24}=7,r_{24}^{\prime }=116016875125$.

$y_{24}=116016875125$.

$$x_{24}=1211251736511.$$

$$s_{24}=-4.$$

${\rho }_{25}=1,{\rho }_{25}^{\prime }=-331817152909$. Take $r_{25}=1-4k_{25}=9$. Then $r_{25}^{\prime }=-563850903159$.

$y_{25}=-563850903159$.

$$x_{25}=.-5886776254306.$$

$$s_{25}=7.$$

$r_{26}=5,r_{26}^{\prime }=-1243718681443$.

$y_{26}=-1243718681443$.

$$x_{26}=-12984804245123.$$

$$s_{26}=.-12.$$

$r_{27}=7,r_{27}^{\prime }=1807569584602$.

$y_{27}=1807569584602$.

$$x_{27}=18871580499429.$$

$$s_{27}=5.$$

${\rho }_{28}=3,{\rho }_{28}^{\prime }=4858857850647$. Take $r_{28}=3+5k_{28}=8$. Then $r_{28}^{\prime }=6666427435249$.

$y_{28}=6666427435249$.

$$x_{28}=69599545743410.$$

$$s_{28}=-9.$$

${\rho }_{29}=1,{\rho }_{29}^{\prime }=-8473997019851$. Take $r_{29}=1+9k_{29}=10$. Then $r_{29}^{\prime }=-15140424455100$.

$y_{29}=-15140424455100$.

$$x_{29}=-158070671986249.$$

$$s_{29}=1.$$

Therefore

$${158070671986249}^2-109\cdot {15140424455100}^2=1.$$

Thus $\sqrt{109}\sim \frac{158070671986249}{15140424455100}$.