next up previous
Next: Proof of Main Theorem Up: Continued Fraction Factorization Previous: Matrix Representations and Fractional

Theorems of Special Interest

Lemma 1   : $\{a_0,a_1,\ldots,a_{n-1}\}(\frac{1}{a_n})=\frac{1}{[a_0,a_1,\ldots,a_n]}$, for all $n \in \mathbb{N}$.

Proof: Let $n=1$. Then

\begin{displaymath}
\{a_0\}\left(\frac{1}{a_1}\right)=
\left
(\begin{array...
...}\right)=\frac{1}{a_0+\frac{1}{a_1}}=
\frac{1}{[a_0,a_1]}.
\end{displaymath}

Thus the statement is true for the base case. Now assume that the statement is true for some $k \in \mathbb{N}$ and let $n=k+1$. We must show that

\begin{displaymath}
\{a_0,a_1,\ldots,a_k\}\left(\frac{1}{a_{k+1}}\right)=\frac{1}{[a_0,a_1,\ldots,a_{k+1}]}.
\end{displaymath}

By assumption, $\{a_0,a_1,\ldots,a_{k-1}\}(\frac{1}{a_k})=\frac{1}{[a_0,a_1,\ldots,a_k]}$, so we have

\begin{displaymath}
\{a_0,a_1,\ldots,a_k\}\left(\frac{1}{a_{k+1}}\right)=
\{a_0,a_1,\ldots,a_{k-1}\}\{a_k\}\left(\frac{1}{a_{k+1}}\right)=
\end{displaymath}


\begin{displaymath}
\{a_0,a_1,\ldots,a_{k-1}\}\left(\frac{1}{[a_k,a_{k+1}]}\right)=
\frac{1}{[a_0,a_1,\ldots,a_{k-1},[a_k,a_{k+1}]]}=
\end{displaymath}


\begin{displaymath}
\frac{1}{[a_0,a_1,\ldots,a_{k+1}]}
\end{displaymath}

as required. Thus we conclude by induction that the statement is true for all $n \in \mathbb{N}$. $\blacksquare$

Theorem 1   : Let $x \in \mathbb{R}$. Then $x=[a_0,a_1,a_2,\ldots,a_n]$ if and only if

\begin{displaymath}
\frac{1}{x} = \{a_0,a_1,\ldots,a_{n-1}\}(\frac{1}{a_n}).
\end{displaymath}

Proof: Assume that $x=[a_0,a_1,\ldots,a_n]$. By Lemma 1, $\{a_0,a_1,\ldots,a_{n-1}\}(\frac{1}{a_n})=\frac{1}{[a_0,a_1,\ldots,a_n]}$. But $\frac{1}{[a_0,a_1,\ldots,a_n]}=\frac{1}{x}$, so $\{a_0,a_1,\ldots,a_{n-1}\}(\frac{1}{a_n})=\frac{1}{x}$ as required. Conversely, assume that $\{a_0,a_1,\ldots,a_{n-1}\}(\frac{1}{a_n})=\frac{1}{x}$. Again by Lemma 1, $\{a_0,a_1,\ldots,a_{n-1}\}(\frac{1}{a_n})=\frac{1}{[a_0,a_1,\ldots,a_n]}$ so $\frac{1}{x}=\frac{1}{[a_0,a_1,\ldots,a_n]}$. Thus $x=[a_0,a_1,\ldots,a_n]$ and we are done. $\blacksquare$

For the remainder of this report, let $x \in \mathbb{R}$ and let $\bar{x}$ denote the conjugate of $x$.

Theorem 2   : The continued fraction expansion of $x$ is purely periodic if and only if $-1<\bar{x}<0$.

Proof: Suppose that the continued fraction expansion of $x$ is purely periodic. Then this expansion is of the form $x=[\overline{a_0,a_1,\ldots,a_n}]=[a_0,a_1,\ldots,a_n,x]$. Let $\left
(\begin{array}{cc}
a & b\\
c & d
\end{array} \right)
= \{a_0,a_1,\ldots,a_n\}$. Then by Theorem 1,

\begin{displaymath}
\left
(\begin{array}{cc}
a & b\\
c & d
\end{array...
... \left(\frac{1}{x}\right) = \frac{a+bx}{c+dx} = \frac{1}{x}.
\end{displaymath}

Rearranging terms we obtain the quadratic equation $bx^2+(a-d)x-c=0$. Solving for x we have

\begin{displaymath}
x=\frac{(d-a) \pm \sqrt{(a-d)^2+4bc}}{2b}.
\end{displaymath} (6)


But since det $\left
(\begin{array}{cc}
a & b\\
c & d
\end{array} \right) = \pm 1$, $ad-bc=\pm 1$ so $4ad \mp 4=4bc$. Substituting in (6) we have

\begin{displaymath}
x=\frac{(d-a) \pm \sqrt{(a-d)^2+4ad \mp 4}}{2b}
=\frac{(d-a) \pm \sqrt{(a+d)^2 \mp 4}}{2b}.
\end{displaymath}

Since $(a+d)^2  \mp 4$, $\sqrt{(a+d)^2 \mp 4} \thickapprox (a+d)$. Thus

\begin{displaymath}
x=\frac{d}{b} \quad \textrm{and} \quad \bar{x}=-\frac{a}{b}.
\end{displaymath}

By the construction of $\left
(\begin{array}{cc}
a & b\\
c & d
\end{array} \right)$, $a<b<d$, $a<c<d$, $a=Q_{n-1}$, $b=Q_n$, $c=P_{n-1}$, and $d=P_n$. Thus $x=\frac{d}{b} > 1$. By properties of convergents, $b=Q_n=a_nQ_{n-1}+Q_{n-2}$. Thus rewriting $\bar{x}=-\frac{a}{b}$ as $\bar{x}=-\frac{1}{\frac{b}{a}}$ we see that

\begin{displaymath}
\bar{x}=-\frac{1}{\frac{a_nQ_{n-1}+Q_{n-2}}{Q_{n-1}}}=-\frac{1}{a_n+\frac{Q_{n-2}}{Q_{n-1}}}.
\end{displaymath}

It follows that $-1<\bar{x}<0$.

(This proof of the converse, and an alternate, more precise proof of the above, can be found in [2])
Conversely, suppose that $x>1$ and $-1<\bar{x}<0$. Let $x_0=x$ and recursively define

\begin{displaymath}
\overline{x_{i+1}^{-1}}=\overline{x_i}-a_i.
\end{displaymath}

Since $x_0>1$, $a_i \ge 1$ for all $i \ge 0$. Therefore, if $\overline{x_i}<0$, then $\overline{x_{i+1}^{-1}}<-1$ and $-1<\overline{x_{i+1}}<0$. Because $\overline{x_i}
=a_i+\overline{x_{i+1}^{-1}}$, it follows by induction that $-1<\overline{x_i}<0$ for all $i \ge 0$. Thus we have that

\begin{displaymath}
0<-\overline{x_{i+1}^{-1}}-a_i<1 \quad \textrm{or} \quad a=[-1/\overline{x_{i+1}}].
\end{displaymath}

Since $x$ is a quadratic irrational, it must be that $x_j=x_k$ for some $j,k \in
\mathbb{Z}$ with $0<j<k$. Then $\overline{x_j}=\overline{x_k}$ and

\begin{displaymath}
a_{j-1}=[-1/\overline{x_j}]=[-1/\overline{x_k}]=a_{k-1}.
\end{displaymath}

It is also true that

\begin{displaymath}
x_{j-1}=a_{j-1}+\frac{1}{x_j}=a_{k-1}+\frac{1}{x_k}=x_{k-1}.
\end{displaymath}

Thus $x_j=x_k$ implies that $x_{j-1}=x_{k-1}$. Doing this $j$ times yields

\begin{displaymath}
x_0=x_{k-j} \quad \textrm{and hence} \quad x=x_0=[\overline{a_0;a_1,a_2,\ldots,a_{k-j-1}}]
\end{displaymath}

as required. $\blacksquare$

Let $a_0$ be the greatest integer in $\sqrt{d}$ and let $x=a_0+\sqrt{d}$. Then obviously$, x$ is larger than $0$and $\bar{x}=a_0-\sqrt{d}$ is strictly between $-1$ and $0$. Thus applying the previous theorem, the continued fraction expansion of $x$ must be purely periodic. In fact we see that

\begin{displaymath}
x=a_0+[a_0;\overline{a_1,a_2,\ldots,a_2,a_1,2a_0}]
\end{displaymath}


\begin{displaymath}
=[\overline{2a_0;a_1,a_2,\ldots,a_2,a_1}]=[2a_0,a_1,a_2,\ldots,a_2,a_1,x].
\end{displaymath} (7)


Applying Theorem 1, we see that $x=[2a_0,a_1,a_2,\ldots,a_2,a_1,x]$ if and only if $\frac{1}{x}=\{2a_0,a_1,a_2,\ldots,a_2,a_1\}(\frac{1}{x})$. Thus we have the following corollary to Theorem 1 (in matrix notation).

Corollary 1 (to Theorem 1)   : Let $d$ be a square-free integer whose continued fraction representation has a center, $a_0$ be the greatest integer in $\sqrt{d}$, $M$ as defined in (4), and $x=a_0+\sqrt{d}$. Then $x=[\overline{2a_0,a_1,a_2,\ldots,a_n,a_0,a_n,\ldots,a_2,a_1}]$ if and only if

\begin{displaymath}
\frac{1}{x} = \{2a_0\}M\{a_0\}M^T\left(\frac{1}{x}\right).
\end{displaymath}

The following proposition will also be useful. A proof can be found in Justin Miller's report: Families of Continued Fractions.

Proposition 1   : Let $x=[a_0,\overline{a_1,a_2,\ldots,a_2,a_1,2a_0}]$. Then $x=\sqrt{d}$ if and only if

\begin{displaymath}
M(\sqrt{d})=\frac{1}{\sqrt{d}}
\end{displaymath}

where $M=\{a_0,a_1,\ldots,a_1,a_0\}$, and $M(\sqrt{d})$ is a fractional linear transformation.

Using this proposition it follows that if $a_0=b$, then

\begin{displaymath}
\frac{1}{\sqrt{d}}=\{a_0\}M\{a_0\}M^T\{a_0\}(\sqrt{d})
\end{displaymath}


\begin{displaymath}
=\frac{\scriptstyle(2CD + D^2a_0)\sqrt{d} + (BC + AD + BDa...
...a_0 + 2BCa_0 +
2ADa_0 + 2BDa_0^2 + 2CDa_0^2 + D^2a_0^3)}.
\end{displaymath}

Solving for $d$ yields

\begin{displaymath}
d=\frac{2AB+2BCa_0+B^2a_0+2ADa_0+2BDa_0^2+2CDa_0^2+D^2a_0^3}{2CD+D^2a_0}.
\end{displaymath} (8)



next up previous
Next: Proof of Main Theorem Up: Continued Fraction Factorization Previous: Matrix Representations and Fractional

scanez 2000-12-04