Exercise 7.7.3 (Expansion of $\sqrt{15}$ into continued fraction)

Question

Expand $\sqrt{15}$ into an infinite simple continued fraction.

Richard Ganaye · Accepted Answer

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

Note: By using (7.16) and the formula from Theorem 4.1.6:
$$
\left \lfloor \frac{a}{n} ight floor = \left \lfloor \frac{\lfloor a floor }{n} ight floor \qquad (n \in \N^*,\ a \in \R)
$$
we obtain
$$a_i = \lfloor \xi_i floor = \left \lfloor \frac{m_i + \sqrt{d}}{q_i} ight floor = \left \lfloor \frac{m_i + \lfloor \sqrt{d} floor }{q_i} ight floor.$$
So we can use only arithmetical operations to compute $a_i$.
\begin{proof} 
Starting from $\xi_0 = \lfloor \sqrt{15} floor +  \sqrt{15} = 3 + \sqrt{15} = \frac{m_0 + \sqrt{d}}{q_0}$, we repeat  (7.13), using the preceding note, until $q_i = 1$ (by Theorem 7.21). We obtain
\begin{align*}
&m_0 = 3,\qquad q_0 = 1, \qquad a_0 = \lfloor \xi floor = 6,\
&m_1 = a_0 q_0 -m_0 = 3,\qquad q_1 =\frac{d - m_{1}^2}{q_0} = 6,\qquad a_1 = \frac{m_1 + \lfloor \sqrt{d} floor}{q_1} = 1,\
&m_2 = a_1 q_1 - m_1 = 3,\qquad q_2 = \frac{d - m_{2}^2}{q_1} = 1.
\end{align*}
Since $q_2 = 1$, there is no other computing, and $3 + \sqrt{15} = \langle \overline{6,1} angle =\langle 6, \overline{1,6} angle$, so
$$\sqrt{15} = \langle 3, \overline{1,6} angle = \langle 3, 1,6,1,6,1,6,1,6,\ldots angle.$$

\end{proof}

The following program in pure Python computes the continued fraction expansion of $\sqrt{n}$:
\begin{verbatim}
from math import sqrt

def continued_fraction(d):
    """ input : d > 1 , not a perfect square
        output: continued fraction expansion of sqrt(d),
          (up to the end of the period)
    """
    Vd = int(sqrt(d))
    expansion = [Vd]
    m = Vd
    q = d - m * m 
    while q != 1:
        a = (m + Vd) // q
        expansion.append(a)
        m = a * q - m; q = (d - m * m) // q 
    expansion.append(m + Vd)
    return expansion
    
if __name__ == '__main__': 
    for i in range(100):
        if int(round(sqrt(i))) ** 2 != i:
    	    print(i, '=>', continued_fraction(i))
	    
2 => [1, 2]
3 => [1, 1, 2]
5 => [2, 4]
6 => [2, 2, 4]
7 => [2, 1, 1, 1, 4]
...
15 => [3, 1, 6]
...
98 => [9, 1, 8, 1, 18]
99 => [9, 1, 18]
\end{verbatim}

This confirms
$$\sqrt{15} = \langle 3 , \overline{1,6} angle.$$

Exercise 7.7.3 (Expansion of $\sqrt{15}$ into continued fraction)

Answers

Comments

Exercise 7.7.3 (Expansion of $\sqrt{15}$ into continued fraction)

Answers

Comments

Add answer