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

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

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

• Prof. Lubin, can you think of a reference for this? I cannot get it to work yet. Note that I have programmed Gauss/Lagrange's method of neighboring reduced forms, as described in Buell, Binary Quadratic Forms. I also don't see how to revise their method to get something of the shape you describe. Dickson's History does not appear to talk about this, at least not in terms i recognize – Will Jagy Apr 15 '17 at 0:48
• The complete cycle of reduced forms equivalent to $x^2 - 67 y^2$ is $\langle 1, 16, -3 \rangle,$ $\langle -3, 14, 6 \rangle,$ $\langle 6, 10, -7 \rangle,$ $\langle -7, 4, 9 \rangle,$ $\langle 9, 14, -2 \rangle,$ $\langle -2, 14, 9 \rangle,$ $\langle 9, 4, -7 \rangle,$ $\langle -7, 10, 6 \rangle,$ $\langle 6, 14, -3 \rangle,$ $\langle -3, 16, 1 \rangle,$ $\langle 1, 16, -3 \rangle.$ including repeating the beginning form – Will Jagy Apr 15 '17 at 0:57
• No reference, @WillJagy, I just analyzed what I do when I calculate the c.f. by repeated derationalization of the denominator. “Cannot get it to work yet” — do you mean that you tried the algorithm above and it gave a different result? – Lubin Apr 15 '17 at 2:01

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

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:

• Once upon a time, I taught a course for high-school teachers in which this stuff was a segment. I (thought I) demonstrated that for $\sqrt n$, the pattern is symmetric, as well as the proposition that all the partial denominators but the last are $\le n$, and when this does occur it’s the middle of the pattern. Tried recently to reconstruct my proofs for these last statements, and hit a snag. – Lubin Apr 15 '17 at 19:13
• i appreciate you – M. A. SARKAR May 3 '17 at 17:03