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

2 Answers 2

10
$\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$
8
  • $\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, 2017 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, 2017 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, 2017 at 2:01
  • $\begingroup$ @Lubin Question: does the repeating section always begin at the first term, or can some numbers lead to a sequence [ a,b,c,d,(repeat_section)] ? $\endgroup$ Feb 14, 2022 at 14:24
  • 1
    $\begingroup$ If you’re taking the square root of a nonsquare integer, @CarlWitthoft , it always starts at the first term. You’ll get an initial nonperiodic segment if your expression is not integral, I think. In any case, the algorithm works only for $\sqrt n$. $\endgroup$
    – Lubin
    Feb 14, 2022 at 16:48
5
$\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} $$

$$ \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}$ 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$
5
  • 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, 2017 at 19:13
  • $\begingroup$ i appreciate you $\endgroup$
    – MAS
    May 3, 2017 at 17:03
  • $\begingroup$ I notice that five years ago I could not reconstruct my argument for the symmetry of the pattern by using “my” algorithm. More recently, I got an argument for that. $\endgroup$
    – Lubin
    Feb 14, 2022 at 16:53
  • $\begingroup$ @Lubin I see, in 2017 you said you did not have the proofs you used for the high-school teachers. Have you posted those anywhere? $\endgroup$
    – Will Jagy
    Feb 14, 2022 at 18:19
  • $\begingroup$ No, @WillJagy, that was when I was teaching at Bowdoin, 1962-66, long before electrons were discovered. $\endgroup$
    – Lubin
    Feb 15, 2022 at 3:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .