5
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Will Jagy Apr 15 '17 at 0:48
  • $\begingroup$ 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 $\endgroup$ – Will Jagy Apr 15 '17 at 0:57
  • 1
    $\begingroup$ 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? $\endgroup$ – Lubin Apr 15 '17 at 2:01
4
$\begingroup$

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}$ enter image description here Perron does (on just one page) show the diagram I have been calling a tableau. He calls it a Schema: enter image description here enter image description here

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Lubin Apr 15 '17 at 19:13
  • $\begingroup$ i appreciate you $\endgroup$ – M. A. SARKAR May 3 '17 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.