Continued fraction of $\sqrt{D}$

169 Views Asked by At

Let $\sqrt{D}=[a_0;\overline{a_1,\cdots,a_k}],$ where $k$ is the length of circulating part, we know $a_k=2a_0.$

Denote $r_j=[\overline{a_j,a_{j+1},\cdots,a_{j+k-1}}]$, where $a_{j+k}=a_j,j>0.$

Prove that $r_1 r_2\cdots r_k=x+y\sqrt{D},$ where $x,y$ is the least positive integer solution to $x^2-Dy^2=(-1)^k.$

For example, $D=14,\sqrt{14}=[3,\overline{1,2,1,6}],k=4.$ $$r_1=[\overline{1,2,1,6}]=\frac{3+\sqrt{14}}{5},\\ r_2=[\overline{2,1,6,1}]=\frac{2+\sqrt{14}}{2},\\ r_3=[\overline{1,6,1,2}]=\frac{2+\sqrt{14}}{5},\\ r_4=[\overline{6,1,2,1}]=3+\sqrt{14},\\ r_1r_2r_3r_4=15+4\sqrt{14},$$ and $15^2-14 \times 4^2=1.$

1

There are 1 best solutions below

0
On BEST ANSWER

For $j=0,1,2,\ldots$, let $p_j$ and $q_j$ be integers such that $q_j>0$, $\gcd(p_j,q_j)=1$, and $\dfrac{p_j}{q_j}$ is the $j$-th convergent of $$\sqrt{D}-a_0=\left[0;\overline{a_1,a_2,\ldots,a_k}\right]\,.$$ In partcular, $p_0=0$ and $q_0=1$. Write $r_{k+1}:=r_1$, $p_{-1}=1$, and $q_{-1}=0$. Show that $$p_j=a_jp_{j-1}+p_{j-2}$$ and $$q_j=a_jq_{j-1}+q_{j-2}$$ for every integer $j\geq 1$.

From $$r_j=a_j+\frac{1}{r_{j+1}}$$ for all $j=1,2,\ldots,k$, we see that $$r_1r_2\ldots r_j=q_{j}+\frac{q_{j-1}}{r_{j+1}}$$ for all $j=1,2,\ldots,k$. In particular, this means $$r_1r_2\cdots r_k=q_{k}+\frac{q_{k-1}}{r_{k+1}}=q_{k}+\frac{q_{k-1}}{r_1}\,.$$ Since $\sqrt{D}=a_0+\dfrac{1}{r_1}$, we have $$\sqrt{D}-a_0=\dfrac{1}{r_1}\,,$$ so $$r_1r_2\cdots r_k=q_{k}+\left(\sqrt{D}-a_0\right)\,q_{k-1}=\left(q_{k}-a_0q_{k-1}\right)+q_{k-1}\sqrt{D}$$

Now $q_k=a_kq_{k-1}+q_{k-2}=2a_0q_{k-1}+q_{k-2}$, whence $$r_1r_2\cdots r_k=\left(q_{k-2}+a_0q_{k-1}\right)+q_{k-1}\sqrt{D}\,.$$ It is known that the smallest positive integers $x$ and $y$ such that $\left|x^2-Dy^2\right|=1$ are , respectively, the numerator and the denominator of the $(k-1)$-st convergent of $\sqrt{D}$, and in fact, $$x^2-Dy^2=(-1)^k\,.$$ Since $a_0+\dfrac{p_{k-1}}{q_{k-1}}=\dfrac{p_{k-1}+a_0q_{k-1}}{q_{k-1}}$ is the $(k-1)$-st convergent of $\sqrt{D}$, it suffices to show that $$p_{k-1}=q_{k-2}\,.$$ The case $k=1$ is obvious. We assume that $k\geq 2$ from now on.

Claim. For every integer $n\geq 0$, there exists a polynomial $$P_n(x_1,x_2,\ldots,x_{n})\in\mathbb{Z}[x_1,x_2,\ldots,x_{n}]$$ such that $$P_n(x_1,x_2,\ldots,x_{n-1},x_n)=P_n(x_n,x_{n-1},\ldots,x_2,x_1)$$ (that is, $P_n$ is "palindromic" in its variables), $$p_{n+1}=P_n(a_{n+1},a_n,\ldots,a_3,a_{2})\,,$$ and $$q_n=P_n(a_1,a_2,\ldots,a_{n-1},a_{n})\,.$$

Proof of Claim.

Define $P_0:=1$, $P_1(x_1):=x_1$, and $$P_n\left(x_1,x_2,\ldots,x_n\right):=x_n\,P_{n-1}\left(x_1,x_2,\ldots,x_{n-1}\right)+P_{n-2}\left(x_1,x_2,\ldots,x_{n-2}\right)$$ for every integer $n\geq 2$. We need to only show that $P_n$ is palindromic in its variables, and the other requirements follow immediately.

We shall prove by induction. The palindromic property holds trivially for $P_0$, $P_1$, $P_2$, $P_3$, and $P_4$. Let $n\geq 5$ be an integer. Suppose that all $P_0,P_1,P_2,\ldots,P_{n-1}$ are palindromic. We see that $$\begin{align}P_n(x_n,x_{n-1},\ldots,x_{2},x_1)&=x_1\,P_{n-1}(x_{n},x_{n-1},\ldots,x_3,x_{2})+P_{n-2}(x_n,x_{n-1},\ldots,x_4,x_{3}) \\&=x_1\,P_{n-1}(x_{2},x_3,\ldots,x_{n-1},x_n)+P_{n-2}(x_{3},x_4,\ldots,x_{n-1},x_n) \\&=x_1\,\Big(x_n\,P_{n-2}(x_{2},x_3,\ldots,x_{n-2},x_{n-1})+P_{n-3}(x_{2},x_3,\ldots,x_{n-3},x_{n-2})\Big)\\&\phantom{aaaaa}+\Big(x_n\,P_{n-3}(x_{3},x_4,\ldots,x_{n-2},x_{n-1})+P_{n-4}(x_{3},x_4,\ldots,x_{n-3},x_{n-2})\Big) \\&=x_1x_n\,P_{n-2}(x_{2},x_3,\ldots,x_{n-2},x_{n-1})+x_1\,P_{n-3}(x_{2},x_3,\ldots,x_{n-3},x_{n-2}) \\&\phantom{aaaaa}+x_n\,P_{n-3}(x_{3},x_4,\ldots,x_{n-2},x_{n-1})+P_{n-4}(x_{3},x_4,\ldots,x_{n-3},x_{n-2})\,.\end{align}$$ Similarly, $$\begin{align}P_n(x_1,x_{2},\ldots,x_{n-1},x_n)&=x_n\,P_{n-1}(x_{1},x_{2},\ldots,x_{n-2},x_{n-1})+P_{n-2}(x_1,x_{2},\ldots,x_{n-3},x_{n-2}) \\&=x_n\,P_{n-1}(x_{n-1},x_{n-2},\ldots,x_{2},x_1)+P_{n-2}(x_{n-2},x_{n-3},\ldots,x_{2},x_1) \\&=x_n\,\Big(x_1\,P_{n-2}(x_{n-1},x_{n-2},\ldots,x_{3},x_2)+P_{n-3}(x_{n-2},x_{n-3},\ldots,x_{4},x_3)\Big)\\&\phantom{aaaaa}+\Big(x_1\,P_{n-3}(x_{n-2},x_{n-3},\ldots,x_{3},x_2)+P_{n-4}(x_{n-2},x_{n-3},\ldots,x_{4},x_3)\Big) \\&=x_1x_n\,P_{n-2}(x_{n-1},x_{n-2},\ldots,x_{3},x_2)+x_n\,P_{n-3}(x_{n-2},x_{n-3},\ldots,x_{4},x_3) \\&\phantom{aaaaa}+x_1\,P_{n-3}(x_{n-2},x_{n-3},\ldots,x_{3},x_2)+P_{n-4}(x_{n-2},x_{n-3},\ldots,x_{4},x_3)\,.\end{align}$$ By induction hypothesis, $P_n$ is then palindromic in its variables. $$\phantom{a}\tag*{$\Box$}$$

From this claim, we have $$p_{k-1}=P_{k-2}\left(a_{k-1},a_{k-2},\ldots,a_{3},a_2\right)$$ and $$q_{k-2}=P_{k-2}\left(a_1,a_2,\ldots,a_{k-3},a_{k-2}\right)\,.$$ As the continued fraction of $\sqrt{D}$ is palindromic (i.e., $a_1=a_{k-1}$, $a_2=a_{k-2}$, $\ldots$), we get $p_{k-1}=q_{k-2}$ as asserted.