next up previous
Next: Factorization Up: Continued Fraction Factorization Previous: Theorems of Special Interest

Proof of Main Theorem

Lemma 2   : Let $d$ be a square-free integer, $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\left(\frac{2}{x}\right).
\end{displaymath}

Proof: For a proof, see [??].

Theorem 3 (B = 2C)   : Let $d$ be a square-free integer such that the continued fraction representation of $d$ has a center b, $a_0$ be the greatest integer in $\sqrt{d}$, $x=a_0+\sqrt{d}$, and $M=\left(\begin{array}{cc}
A & B\\
C & D
\end{array} \right) $ be defined as in (4). Then $a_0=b$ if and only if $B=2C$.

Proof: Suppose that $a_0=b$. Then $x=[\overline{2a_0,a_1,a_2,\ldots,a_n,a_0,a_n,\ldots,a_2,a_1}]$ so by Lemma 2,

\begin{displaymath}
\frac{1}{x} =
\{2a_0\}
\left(\begin{array}{cc}
A & B...
...
C & D
\end{array} \right)
\left(\frac{2}{x}\right).
\end{displaymath}

which leads to

\begin{displaymath}
\left(\begin{array}{cc}
0 & 1\\
1 & a_0
\end{array}...
...} \right) \left(\frac{1}{x}\right)=\left(\frac{2}{x}\right).
\end{displaymath}

Carrying out this fractional linear transformation yields

\begin{displaymath}
\frac{B+Dx}{A+Ba_0+Cx+Dxa_0}=\frac{2}{x}.
\end{displaymath}

Substituting $a_0+\sqrt{d}$ in for $x$ and making the substitution stated in (8) gives the equation

\begin{displaymath}
\scriptscriptstyle 2ABD + a_0B^2D - 4ACD - 4a_0C^2D + 2BC\...
...^2 -
2a_0^2CD^2 + a_0B\sqrt{d}D^2 - 2a_0C\sqrt{d}D^2 = 0.
\end{displaymath}

But by the construction of $M$, det $M$=$AD-BC=\pm 1$. Thus making the substitution $AD=BC\pm 1$ into the above equation, we get the quadratic equation (in B)

\begin{displaymath}
\scriptscriptstyle (2C+AD)B^2 + (-4C^2+2C\sqrt{d}D+a_0^2D^...
...a_0C^2D-4C^2\sqrt{d}D-2a_0^2CD^2-2a_0C\sqrt{d}D^2 \mp 4C)=0.
\end{displaymath}

Solving for $B$ yields

\begin{displaymath}
B=2C \quad \textrm{or} \quad B=\frac{-2a_0CD-2C\sqrt{d}D-a_0^2D^2-a_0\sqrt{d}D^2 \mp 2}{2C+a_0D}.
\end{displaymath} (9)


But by the choice of $d$ and the construction of $A,B,C,$ and $D$, we have that $d,A,B,C,D>0$ and thus the second possibility must be ruled out because it would yield a negative value for $B$. Hence $B=2C$ as required. Conversly, assume that $B=2C$. Then it is true that

\begin{displaymath}
\scriptscriptstyle (2C+AD)B^2 + (-4C^2+2C\sqrt{d}D+a_0^2D^...
...a_0C^2D-4C^2\sqrt{d}D-2a_0^2CD^2-2a_0C\sqrt{d}D^2 \mp 4C)=0.
\end{displaymath}

But once again, $AD-BC=\pm 1$ so if we make the substitution $AD=BC\pm 1$, it is true that

\begin{displaymath}
\scriptscriptstyle 2ABD + a_0B^2D - 4ACD - 4a_0C^2D + 2BC\...
...^2 -
2a_0^2CD^2 + a_0B\sqrt{d}D^2 - 2a_0C\sqrt{d}D^2 = 0.
\end{displaymath}

Then making the substitution $x=a_0+\sqrt{d}$ and the one stated in (8) yields (after rearranging terms)

\begin{displaymath}
\frac{B+Dx}{A+Ba_0+Cx+Dxa_0}=\frac{2}{x}.
\end{displaymath}

It follows that

\begin{displaymath}
\frac{1}{x}
=\{2a_0\}
\left(\begin{array}{cc}
A & B\\
C & D
\end{array} \right)
\left(\frac{2}{x}\right)
\end{displaymath}

and thus by Lemma 2, $x=[\overline{2a_0,a_1,a_2,\ldots,a_n,a_0,a_n,\ldots,a_2,a_1}]$and $a_0=b$. $\blacksquare$

For the remainder of the report we consider those continued fractions such that $a_0=b$. Then we can make a change of variables in the matrix $M$ in (4) and let

\begin{displaymath}
M=
\left
(\begin{array}{cc}
A & 2B\\
B & C
\end{array} \right)
\end{displaymath} (10)



next up previous
Next: Factorization Up: Continued Fraction Factorization Previous: Theorems of Special Interest

scanez 2000-12-04