Continued fraction of $\sqrt{67} - 4$

Question

Find the continued fraction of $ \sqrt{67}-4 $ . $$ $$ We Know that if $ N $ is not a perfect square and if continued fraction of $ \sqrt N $ is $ \sqrt N = [a_{1} , \overline {a_{2},a_{3} , \ldots , 2a_{1}} ]$ , then the continued fraction of $ \sqrt N-a_{1}$ is $ \sqrt N-a_{1}=[\overline {0,a_{2},a_{3},\ldots,a_{n}, 2a_{1}}] $ . But I can't find the continued fraction of $\sqrt {67} $. Please someone help me

Answer 1

The regular continued fraction expansion of $\sqrt{67}$ is $$ 8+\frac1{5+}\frac1{2+}\frac1{1+}\frac1{1+}\frac1{7+}\frac1{1+}\frac1{1+}\frac1{2+}\frac1{5+}\frac1{16+}\cdots\>, $$ and the repeating part is the whole segment between the “$\frac1{5+}$” and the “$\frac1{16+}$”.

You may get it by a repeated process of “derationalizing the denominator”, starting with $$ \frac{\sqrt{67}-8}1=\frac3{\sqrt{67}+8}=\frac1{\bigl(\sqrt{67}+8\bigr)\big/3} =\frac1{5+}\frac{\sqrt{67}-7}3\,,\quad\text{etc.} $$

But here’s an algorithm that mechanizes the whole process, I’m sure it’s well known:
If $N$ is a nonsquare positive integer, put $m=\lfloor \sqrt N\rfloor$, and start with the pair $(p,q)=(m,1)$, then, recursively, put \begin{align} q'&=\frac{N-p^2}q\\ d&=\left\lfloor\frac{p+m}{q'}\right\rfloor\\ p'&=dq'-p\quad. \end{align} Then the “output” $d$ of this step is the partial denominator that you will see in the continued-fraction expansion. And the process repeats after the first appearance of $d=2m$.

Answer 2

Typeset the hand calculation method Prof. Lubin indicated. I would say that the reason I did not know this was that I had never calculated one of these by hand. There is a lesson in that.

$$ \sqrt { 67} = 8 + \frac{ \sqrt {67} - 8 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {67} - 8 } = \frac{ \sqrt {67} + 8 }{3 } = 5 + \frac{ \sqrt {67} - 7 }{3 } $$ $$ \frac{ 3 }{ \sqrt {67} - 7 } = \frac{ \sqrt {67} + 7 }{6 } = 2 + \frac{ \sqrt {67} - 5 }{6 } $$ $$ \frac{ 6 }{ \sqrt {67} - 5 } = \frac{ \sqrt {67} + 5 }{7 } = 1 + \frac{ \sqrt {67} - 2 }{7 } $$ $$ \frac{ 7 }{ \sqrt {67} - 2 } = \frac{ \sqrt {67} + 2 }{9 } = 1 + \frac{ \sqrt {67} - 7 }{9 } $$ $$ \frac{ 9 }{ \sqrt {67} - 7 } = \frac{ \sqrt {67} + 7 }{2 } = 7 + \frac{ \sqrt {67} - 7 }{2 } $$ $$ \frac{ 2 }{ \sqrt {67} - 7 } = \frac{ \sqrt {67} + 7 }{9 } = 1 + \frac{ \sqrt {67} - 2 }{9 } $$ $$ \frac{ 9 }{ \sqrt {67} - 2 } = \frac{ \sqrt {67} + 2 }{7 } = 1 + \frac{ \sqrt {67} - 5 }{7 } $$ $$ \frac{ 7 }{ \sqrt {67} - 5 } = \frac{ \sqrt {67} + 5 }{6 } = 2 + \frac{ \sqrt {67} - 7 }{6 } $$ $$ \frac{ 6 }{ \sqrt {67} - 7 } = \frac{ \sqrt {67} + 7 }{3 } = 5 + \frac{ \sqrt {67} - 8 }{3 } $$ $$ \frac{ 3 }{ \sqrt {67} - 8 } = \frac{ \sqrt {67} + 8 }{1 } = 16 + \frac{ \sqrt {67} - 8 }{1 } $$

My favorite tableau for a simple continued fraction:
$$ \small \begin{array}{cccccccccccccccccccccccccc} & & 8 & & 5 & & 2 & & 1 & & 1 & & 7 & & 1 & & 1 & & 2 & & 5 & & 16 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 8 }{ 1 } & & \frac{ 41 }{ 5 } & & \frac{ 90 }{ 11 } & & \frac{ 131 }{ 16 } & & \frac{ 221 }{ 27 } & & \frac{ 1678 }{ 205 } & & \frac{ 1899 }{ 232 } & & \frac{ 3577 }{ 437 } & & \frac{ 9053 }{ 1106 } & & \frac{ 48842 }{ 5967 } \\ \\ & 1 & & -3 & & 6 & & -7 & & 9 & & -2 & & 9 & & -7 & & 6 & & -3 & & 1 \end{array} $$ $$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 67 \cdot 0^2 = 1 & \mbox{digit} & 8 \\ \frac{ 8 }{ 1 } & 8^2 - 67 \cdot 1^2 = -3 & \mbox{digit} & 5 \\ \frac{ 41 }{ 5 } & 41^2 - 67 \cdot 5^2 = 6 & \mbox{digit} & 2 \\ \frac{ 90 }{ 11 } & 90^2 - 67 \cdot 11^2 = -7 & \mbox{digit} & 1 \\ \frac{ 131 }{ 16 } & 131^2 - 67 \cdot 16^2 = 9 & \mbox{digit} & 1 \\ \frac{ 221 }{ 27 } & 221^2 - 67 \cdot 27^2 = -2 & \mbox{digit} & 7 \\ \frac{ 1678 }{ 205 } & 1678^2 - 67 \cdot 205^2 = 9 & \mbox{digit} & 1 \\ \frac{ 1899 }{ 232 } & 1899^2 - 67 \cdot 232^2 = -7 & \mbox{digit} & 1 \\ \frac{ 3577 }{ 437 } & 3577^2 - 67 \cdot 437^2 = 6 & \mbox{digit} & 2 \\ \frac{ 9053 }{ 1106 } & 9053^2 - 67 \cdot 1106^2 = -3 & \mbox{digit} & 5 \\ \frac{ 48842 }{ 5967 } & 48842^2 - 67 \cdot 5967^2 = 1 & \mbox{digit} & 16 \\ \end{array} $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

I also did 73 which seems to be the only example in Perron(1913) $$ \sqrt { 73} = 8 + \frac{ \sqrt {73} - 8 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {73} - 8 } = \frac{ \sqrt {73} + 8 }{9 } = 1 + \frac{ \sqrt {73} - 1 }{9 } $$ $$ \frac{ 9 }{ \sqrt {73} - 1 } = \frac{ \sqrt {73} + 1 }{8 } = 1 + \frac{ \sqrt {73} - 7 }{8 } $$ $$ \frac{ 8 }{ \sqrt {73} - 7 } = \frac{ \sqrt {73} + 7 }{3 } = 5 + \frac{ \sqrt {73} - 8 }{3 } $$ $$ \frac{ 3 }{ \sqrt {73} - 8 } = \frac{ \sqrt {73} + 8 }{3 } = 5 + \frac{ \sqrt {73} - 7 }{3 } $$ $$ \frac{ 3 }{ \sqrt {73} - 7 } = \frac{ \sqrt {73} + 7 }{8 } = 1 + \frac{ \sqrt {73} - 1 }{8 } $$ $$ \frac{ 8 }{ \sqrt {73} - 1 } = \frac{ \sqrt {73} + 1 }{9 } = 1 + \frac{ \sqrt {73} - 8 }{9 } $$ $$ \frac{ 9 }{ \sqrt {73} - 8 } = \frac{ \sqrt {73} + 8 }{1 } = 16 + \frac{ \sqrt {73} - 8 }{1 } $$

Tableau:
$$ \tiny \begin{array}{cccccccccccccccccccccccccccccccc} & & 8 & & 1 & & 1 & & 5 & & 5 & & 1 & & 1 & & 16 & & 1 & & 1 & & 5 & & 5 & & 1 & & 1 & & 16 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 8 }{ 1 } & & \frac{ 9 }{ 1 } & & \frac{ 17 }{ 2 } & & \frac{ 94 }{ 11 } & & \frac{ 487 }{ 57 } & & \frac{ 581 }{ 68 } & & \frac{ 1068 }{ 125 } & & \frac{ 17669 }{ 2068 } & & \frac{ 18737 }{ 2193 } & & \frac{ 36406 }{ 4261 } & & \frac{ 200767 }{ 23498 } & & \frac{ 1040241 }{ 121751 } & & \frac{ 1241008 }{ 145249 } & & \frac{ 2281249 }{ 267000 } \\ \\ & 1 & & -9 & & 8 & & -3 & & 3 & & -8 & & 9 & & -1 & & 9 & & -8 & & 3 & & -3 & & 8 & & -9 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 73 \cdot 0^2 = 1 & \mbox{digit} & 8 \\ \frac{ 8 }{ 1 } & 8^2 - 73 \cdot 1^2 = -9 & \mbox{digit} & 1 \\ \frac{ 9 }{ 1 } & 9^2 - 73 \cdot 1^2 = 8 & \mbox{digit} & 1 \\ \frac{ 17 }{ 2 } & 17^2 - 73 \cdot 2^2 = -3 & \mbox{digit} & 5 \\ \frac{ 94 }{ 11 } & 94^2 - 73 \cdot 11^2 = 3 & \mbox{digit} & 5 \\ \frac{ 487 }{ 57 } & 487^2 - 73 \cdot 57^2 = -8 & \mbox{digit} & 1 \\ \frac{ 581 }{ 68 } & 581^2 - 73 \cdot 68^2 = 9 & \mbox{digit} & 1 \\ \frac{ 1068 }{ 125 } & 1068^2 - 73 \cdot 125^2 = -1 & \mbox{digit} & 16 \\ \frac{ 17669 }{ 2068 } & 17669^2 - 73 \cdot 2068^2 = 9 & \mbox{digit} & 1 \\ \frac{ 18737 }{ 2193 } & 18737^2 - 73 \cdot 2193^2 = -8 & \mbox{digit} & 1 \\ \frac{ 36406 }{ 4261 } & 36406^2 - 73 \cdot 4261^2 = 3 & \mbox{digit} & 5 \\ \frac{ 200767 }{ 23498 } & 200767^2 - 73 \cdot 23498^2 = -3 & \mbox{digit} & 5 \\ \frac{ 1040241 }{ 121751 } & 1040241^2 - 73 \cdot 121751^2 = 8 & \mbox{digit} & 1 \\ \frac{ 1241008 }{ 145249 } & 1241008^2 - 73 \cdot 145249^2 = -9 & \mbox{digit} & 1 \\ \frac{ 2281249 }{ 267000 } & 2281249^2 - 73 \cdot 267000^2 = 1 & \mbox{digit} & 16 \\ \end{array} $$

Note how we need to go twice through the "digits" to get to $1,$ as $$ 1068^2 - 73 \cdot 125^2 = -1 $$ See how Perron (1913) displays the beginning of the calculation for $\sqrt {73}$ Perron does (on just one page) show the diagram I have been calling a tableau. He calls it a Schema: