\documentclass[12pt,leqno]{article} \usepackage{amssymb,amsmath} \renewcommand{\baselinestretch}{1.2} %This is the command that spaces the manuscript for easy reading % $b^{2} \equiv D \; (\bmod{~4})$ \begin{document} \begin{center} \begin{large} Continued Fractions for $\sqrt{D}$ and $(1+\sqrt{D})/2$ \end{large} ~ John P. Robertson JPR2718@AOL.COM Copyright 2003 \end{center} \subsection*{Introduction} For $D>0$ not a square, $D \equiv 1 \pmod{4}$, let $L_1$ ($=L_{1}(D)$) and $L_4$ ($=L_{4}(D)$) denote the lengths of the periods of the continued fraction expansions of $\sqrt{D}$ and $(1+\sqrt{D})/2$ respectively. This note shows that if $L_4 = 3$ then $L_1$ cannot be 7. When $L_4=3$, literature that I am aware of prohibits any values for $L_1$ other than 1, 5, 7, 11, and 15, but I have not seen anything showing that 7 is not possible \cite{williams,ishii}. I would welcome any information as to whether this has been known previously. More generally, I conjecture that if $L_4 \equiv 3 \pmod{6}$, then $L_1$ cannot equal $L_4 + 4$. This last point is not pursued further here. \subsection*{Outline of proof} We start with an outline of the proof. If $L_4=3$, then the continued fraction expansion of $(1 + \sqrt{D})/2$ must be of the form $\left\langle{c; \; \overline{a, \; a, \; b}}\right\rangle$ \cite[p. 252, exercise 5.3.14]{mollin}. Then, using the assumption that $D \equiv 1 \pmod 4$, we can show that there must be an $n > 0$ so that $b = a + n(a^2 + 1)$ and that $b$ is odd. If $a$ is odd, $n$ can be any nonnegative integer, while if $a$ is even, $n$ must be an odd positive integer. Then one simply considers four cases: 1) $a = 1$, in which case $L_1=1$ (because $D$ will turn out to be $s^2 + 1$ for some integer $s$), 2) $a > 1$ is odd, whence $L_1=5$, 3) $a = 2$, whence $L_1 = 11$, and 4) $a > 2$ is even, whence $L_1=15$. In no case is $L_1 = 7$. Proofs of the cases are straightforward: just compute the continued fraction expansion of $\sqrt{D}$ algebraically by the standard method. \subsection*{Background and notation} First we present the PQa algorithm, which computes the (simple) continued fraction expansion of the quadratic irrational $(P_0 + \sqrt{D})/Q_0$ for certain $P_0, Q_0, D$. It also computes some auxiliary variables. Let $P_0, Q_0, D$ be integers so that $Q_0 \ne 0$, $D > 0$ is not a square, and $P_0^2 \equiv D \; (\bmod{~|Q_0|})$. Set $A_{-2} = 0$, $A_{-1} = 1$, $B_{-2} = 1$, and $B_{-1} = 0$. For $i \ge 0$ set \begin{list}{}{\setlength{\leftmargin}{.5in} \setlength{\rightmargin}{.5in}} \item $a_i = \left\lfloor{(P_i + \sqrt{D})/Q_i}\right\rfloor$, \item $A_i = a_i A_{i-1} + A_{i-2}$, \item $B_i = a_i B_{i-1} + B_{i-2}$, \end{list} and for $i \ge 1$ set \begin{list}{}{\setlength{\leftmargin}{.5in} \setlength{\rightmargin}{.5in}} \item $P_i = a_{i-1} Q_{i-1} - P_{i-1}$ and \item $Q_i = (D - P_i^2)/Q_{i-1}$. \end{list} The (simple) continued fraction expansion of $(P_0 + \sqrt{D})/Q_0$ is $\langle a_0, a_1, a_2, \ldots \rangle$ \cite[p. 251, exercise 5.3.6]{mollin}. The convergents to the continued fraction expansion of $(P_0 + \sqrt{D})/Q_0$ are $A_{i}/B_{i}$. We will only use this with $P_0=0$ and $Q_0=1$, or, for $D \equiv 1 \pmod{4}$, with $P_0=1$ and $Q_0=2$. In these cases, all of the $P_i$, $Q_i$, $a_i$, $A_i$, and $B_i$ involved will be positive integers, except possibly $P_0$. Also in these cases, the sequences $P_i$, $Q_i$, and $a_i$ have certain palindromic properties. Namely, if $l$ is the length of the period, then $P_{i} = P_{l+1-i}$ for $i = 1, ~2, ~3, \ldots , l$, $Q_{i}=Q_{l-i}$ for $i = 0, ~1, ~2, \ldots , l$, and $a_{i}=a_{l-i}$ for $i = 1, ~2, ~3, \ldots , l-1$ \cite[p. 242, Corollary 5.3.1; p. 252, exercises 5.3.14 and 5.3.17]{mollin}. In particular, if $l=3$ then $a_1=a_2$. \subsection*{Full proof} Recall that we assume $D>0$ is not a square, and $D \equiv 1 \pmod{4}$. % $b$ = largest odd integer $< \sqrt{D}$ As $L_{4}=3$, the continued fraction of $(1 + \sqrt{D})/2$ is of the form $\left\langle{c; \; \overline{a, \; a, \; b}}\right\rangle$ for positive integers $a$, $b$, and $c$, $a \ne b$, with the $a, \; a, \; b$ repeating, and $b=2c-1$. The continued fraction expansion of $\xi=(2b-2c+1+\sqrt{D})/2$ $=$ $(b+\sqrt{D})/2$ is then $\left\langle{b; \; \overline{a, \; a, \; b}}\right\rangle$, which is purely periodic. Now we establish that $b=a+n(a^2+1)$ for some integer $n>0$, $b$ is odd, and we write $D$ in terms of $a$ and $n$. We have $B_{2}\xi^2 - (A_2 - B_1)\xi - A_1 = 0$ \cite[p. 240]{mollin} where $A_1 = ab+1$, $A_2 = a^{2}b+a+b$, $B_1 = a$, and $B_2 = a^2+1$. This gives $(a^2+1)\xi^2 - (a^{2}b +b)\xi -(ab+1) = 0$. Then \[ \xi=\frac{b(a^2+1) \pm \sqrt{b^{2}(a^2+1)^2 + 4(a^2+1)(ab+1)}}{2(a^2+1)} \] \[ = \frac{b \pm \sqrt{b^2 + \frac{4(ab+1)}{a^2+1}}}{2} \] \noindent The ``$\pm$'' just above must be ``$+$'' because $\xi>0$. Additionally, we must have $D= b^2 + \frac{4(ab+1)}{a^2+1}$, and so $\frac{4(ab+1)}{a^2+1}$ has to be an integer. In fact, this has to be an even integer, since at most one power of 2 can divide $a^2+1$. Because $D$ is odd, $b$ must also be odd. If $\frac{4(ab+1)}{a^2+1}$ is an integer, then $\frac{4(ab+1)}{a^2+1}-4 = \frac{4a(b-a)}{a^2+1}$ is an integer, so $a^2+1$ divides $4(b-a)$ (as $\gcd(a,a^2+1)=1)$. If $a$ is even, then $a^2+1$ is odd, and it must be that $a^2+1$ divides $(b-a)$. Say this quotient is $n$. As $b$ is odd and $a$ is even, $n$ must be odd. We can rewrite this as $b=a+n(a^2+1)$. If $a$ is odd, 2 divides $a^2+1$ but 4 does not. So $(a^2+1)/2$ is odd and divides $b-a$, which is even, so the quotient $k$ is even. Setting $n=k/2$ gives $b=a+n(a^2+1)$ for some integer $n$. There is no restriction on the parity of $n$ when $a$ is odd. Given that $b=a+n(a^2+1)$, we have \[ D=b^2+4(an+1)=n^{2}a^{4} + 2na^{3} + (2n^2+1)a^2 + 6na +n^2+4. \] Also, note that $n>0$, because if $n=0$ then $b=a$ and the length of the period of the continued fraction is 1, not 3. Before moving on to individual cases, we show that if $a=1$ then $\lfloor\sqrt{D}\rfloor = b+1$, while if $a>1$ then $\lfloor\sqrt{D}\rfloor = b$. Clearly, $b^21$. If $a=1$, then $(b+2)^2-D=4(n+1)>0$. So, $(b+1)^2 < D < (b+2)^2$, and $\lfloor\sqrt{D}\rfloor = b+1$. In fact, in this case, $b=2n+1$, and $D=4n^2+8n+5=(2n+2)^2+1$. If $a>1$ then $b^2 < D < (b+1)^2$, so $\lfloor\sqrt{D}\rfloor = b$. %_____________________________________ 1 ______________________________________ Now we turn to the individual cases. First suppose $a=1$. We will show that $L_{1}=1$ in this case. Above we showed that when $a=1$, $D=(2n+2)^2+1$, so $D$ is a square plus 1. It is well known that the continued fraction expansion of $\sqrt{D}$ will have period 1 \cite[p. 253, exercise 5.3.21]{mollin}, but for completeness that calculation is given in Table 1. % table for a = 1. \begin{table} \begin{center} \begin{tabular}{cccc} % \multicolumn{4}{c}{PQa for $a=1$} \\ % $\underline{~i_{~}}$ & $\underline{~P_i~}$ & $\underline{~Q_i~}$ & $\underline{~a_i~}$ \\ \hline $i$ & $P_i$ & $Q_i$ & $a_i$ \\ \hline 0 & 0 & 1 & $b+1$ \\ 1 & $b+1$ & $1$ & $2b+2$ \\ 2 & $b+1$ & $1$ & $2b+2$ \\ \hline \end{tabular} \caption{PQa for $a=1$} \end{center} \end{table} For the second case, suppose $a>1$ is odd. Applying the PQa algorithm algebraically shows the length of the period of the continued fraction expansion of $\sqrt{D}$ is 5, as shown in Table 2. To check that this expansion is correct, one only has to check that \[ P_i=Q_{i-1}a_{i-1}-P_{i-1} \] \[ Q_i=(D-P_i^2)/Q_{i-1}, \; {\rm and} \] \[ 0 \le \frac{P_i+b}{Q_i} - a_i < 1. \] That this last test is valid follows from the fact that, since $b=\lfloor\sqrt{D}\rfloor$, $P_i$ is an integer, and $Q_i$ is a positive integer, \[ \left\lfloor{ \frac{P_i+b}{Q_i} }\right\rfloor = \left\lfloor{ \frac{P_i+\sqrt{D}}{Q_i} }\right\rfloor. \] These equations are easily verified for each index $i$. Table 2 shows $z_i = \frac{P_i+b}{Q_i} - a_i$ written so as to make it easy to verify that $0 \le z_i < 1$. Recall that $a \ge 3$. For the third case, suppose $a=2$. Then $L_{1}=11$ as shown in Table 3. Here everything can be written in terms of $n$; in particular, $b=5n+2$ and $D=25n^2+28n+8$. Finally, for the fourth case, suppose $a>2$ is even. Table 4 shows that $L_{1}=15$. \begin{thebibliography}{99} \bibitem{ishii} Noburo Ishii, Pierre Kaplan, and Kenneth S. Williams, "On Eisenstein's problem," Acta Arithmetica, LIV (1990), pp 323-345. \bibitem{mollin} Richard A. Mollin, Fundamental Number Theory with Applications, CRC Press, Boca Raton, 1998. \bibitem{williams} Kenneth S. Williams and Nicholas Buck, "Comparison of the Lengths of the Continued Fractions of sqrt(D) and (1+sqrt(D))/2," Proceedings of the AMS, v 120, no 4, April 1994, pp 995-1002. \end{thebibliography} %_____________________________________ 2 ______________________________________ % table for a > 1, a odd. \begin{table} \begin{center} \begin{tabular}{ccccc} % \multicolumn{4}{c}{PQa for $a>1$, $a$ odd} \\ % $\underline{~i_{~}}$ & $\underline{~P_i~}$ & $\underline{~Q_i~}$ & $\underline{~a_i~}$ \\ \hline $i$ & $P_i$ & $Q_i$ & $a_i$ & $\frac{P_{i}+b}{Q_{i}} - a_{i}$ \\ \hline 0 & 0 & 1 & $b$ & $0$ \\ 1 & $b$ & $4(an+1)$ & $(a-1)/2$ & $\frac{1}{2} + \frac{1}{2(a+1/n)}$ \\ 2 & $na^2+a-2an-n-2$ & $na^2+a-n$ & $1$ & $1-\frac{2[n(a-1)+1]}{a[n(a-1)+1]+n(a-1)}$ \\ 3 & $2(an+1)$ & $na^2+a-n$ & $1$ & $\frac{2[n(a+1)+1]}{(a-1)[n(a+1)+1]+1}$ \\ 4 & $na^2+a-2an-n-2$ & $4(an+1)$ & $(a-1)/2$ & $0$ \\ 5 & $b$ & $1$ & $2b$ & $0$ \\ 6 & $b$ & $4(an+1)$ & $(a-1)/2$ & $\frac{1}{2} + \frac{1}{2(a+1/n)}$\\ \hline \end{tabular} \caption{PQa for $a>1$, $a$ odd} \end{center} \end{table} %_____________________________________ 3 ______________________________________ % table for a = 2. \begin{table} \begin{center} \begin{tabular}{ccccc} % \multicolumn{4}{c}{PQa for $a=2$} \\ % $\underline{~i_{~}}$ & $\underline{~P_i~}$ & $\underline{~Q_i~}$ & $\underline{~a_i~}$ \\ \hline $i$ & $P_i$ & $Q_i$ & $a_i$ & $\frac{P_{i}+b}{Q_{i}} - a_{i}$ \\ \hline 0 & 0 & 1 & $5n+2$ & $0$ \\ 1 & $5n+2$ & $8n+4$ & $1$ & $n/(4n+2)$ \\ 2 & $3n+2$ & $2n+1$ & $4$ & $0$ \\ 3 & $5n+2$ & $4$ & $(5n+1)/2$ & $1/2$ \\ 4 & $5n$ & $7n+2$ & $1$ & $(3n)/(7n+2)$ \\ 5 & $2n+2$ & $3n+2$ & $2$ & $n/(3n+2)$ \\ 6 & $4n+2$ & $3n+2$ & $2$ & $(3n)/(3n+2)$ \\ 7 & $2n+2$ & $7n+2$ & $1$ & $2/(7n+2)$ \\ 8 & $5n$ & $4$ & $(5n+1)/2$ & $0$ \\ 9 & $5n+2$ & $2n+1$ & $4$ & $(2n)/(2n+1)$ \\ 10 & $3n+2$ & $8n+4$ & $1$ & $0$ \\ 11 & $5n+2$ & $1$ & $10n+4$ & $0$ \\ 12 & $5n+2$ & $8n+4$ & $1$ & $n/(4n+2)$ \\ \hline \end{tabular} \caption{PQa for $a=2$} \end{center} \end{table} %_____________________________________ 4 ______________________________________ % table for a even, a>2. \begin{table} \begin{center} \begin{tabular}{ccccc} % \multicolumn{5}{c}{PQa for $a>2$ even } \\ % $\underline{~i_{~}}$ & $\underline{~P_i~}$ & $\underline{~Q_i~}$ & $\underline{~a_i~}$ & $\underline{\frac{P_{i}+b}{Q_{i}} - a_{i}}$\\ \hline $i$ & $P_i$ & $Q_i$ & $a_i$ & $\frac{P_{i}+b}{Q_{i}} - a_{i}$ \\ \hline 0 & 0 & 1 & $b$ & 0 \\ 1 & $b$ & $4(an+1)$ & $a/2$ & $\frac{1}{2(a \; + \; 1/n)}$ \\ 2 & $b-2n$ & $an+1$ & $2a$ & $0$ \\ 3 & $b$ & $4$ & $(b-1)/2$ & $1/2$ \\ 4 & $b-2$ & $b+na$ & $1$ & $1-\frac{2(na+1)}{a(na+1) \; + \; n(a+1)}$ \\ 5 & $na+2$ & $b-na$ & $1$ & $\frac{2(na+1)}{(a-1)(na+1) \; + \; n \; + \; 1}$ \\ 6 & $b-2na-2$ & $4(na+1)$ & $a/2 - 1$ & $\frac{1}{2} +\frac{1}{2(a \; + \; 1/n)}$ \\ 7 & $b-2na-2n-2$ & $b-2n$ & $1$ & $ 1-\frac{2(1 \; - \; 1/a \; + \; 1/(na))}{a \; - \; 1/a \; + \; 1/n}$ \\ 8 & $2na+2$ & $b-2n$ & $1$ & $\frac{2(1 \; + \; 1/a \; + \; 1/(na))}{a \; - \; 1/a \; + \; 1/n}$ \\ 9 & $b-2na-2n-2$ & $4(na+1)$ & $a/2 - 1$ & $1/2$ \\ 10 & $b-2na-2$ & $b-na$ & $1$ & $1 \; - \; \frac{2}{(a-1)(na) \; + \; n \; + \; a}$\\ 11 & $na+2$ & $b+na$ & $1$ & $2/(b \; + \; na)$ \\ 12 & $b-2$ & $4$ & $(b-1)/2$ & $0$ \\ 13 & $b$ & $an+1$ & $2a$ & $ \frac{2}{a \; + \; 1/n}$ \\ 14 & $b-2n$ & $4(an+1)$ & $a/2$ & $0$ \\ 15 & $b$ & $1$ & $2b$ & $0$ \\ 16 & $b$ & $4(an+1)$ & $a/2$ & $\frac{1}{2(a \; + \; 1/n)}$ \\ \hline \end{tabular} \caption{PQa for $a>2$ even} \end{center} \end{table} \end{document}