Let $[a_0,a_1,a_2,\ldots,a_n,a_n,\ldots,a_2,a_1,a_0]=:\frac{p}{q}\in\mathbb{Q}$ be a symmetric continued fraction. This sequence of $a_i$'s consists of finitely many elements because $\frac{p}{q}$ is rational. I need to prove that $q^2\equiv(-1)^r$ mod $p$ with $r$ the length of the sequence of $a_i$'s.

I'm getting pretty stuck from the beginning. There's a big chance I have to use the property $p_{n-1}q_n-p_nq_{n-1}=(-1)^n$. I guess saying that $\frac{p_n}{q_n}=\frac{p_n}{p_{n-1}}$ would really come in hand for this would prove the statement immedeately, but I don't see/know how to prove this last equality. Any help is appreciated.

Note: the $p_i$'s and $q_i$'s are from the continued fractions of $p$ and $q$ respectively.

Try: By a lemma from my book we can use the following algorithm: $$\begin{bmatrix} p_i&p_{i-1}\\ q_i&q_{i-1} \end{bmatrix} = \begin{bmatrix} p_{i-1}&p_{i-2}\\ q_{i-1}&q_{i-2} \end{bmatrix} \begin{bmatrix} a_i&1\\ 1&0 \end{bmatrix},\ \text{where }\begin{bmatrix} p_{-1}&p_{-2}\\ q_{-1}&q_{-2} \end{bmatrix}=I_2\ \text{and } i\geqslant0.$$

So we have the following using symmetry of the continued fractions: $$\begin{align*}q_0&=1,\\ q_1&=a_1,\\ &\vdots\\q_{n-1}&=a_{1}q_{n-2}+q_{n-3}\ (a_1=a_{n-1}),\\\ q_n&=a_0q_{n-1}+q_{n-2}.\end{align*}$$ We also have: $$\begin{align*} p_0&=a_0,\\ p_1&=a_1p_0+1,\\ &\vdots\\p_{n-1}&=a_{1}p_{n-2}+p_{n-3}\ (a_1=a_{n-1}),\\\ p_n&=a_0p_{n-1}+p_{n-2}. \end{align*}$$ Somehow it should now turn out to be true that $q_n=p_{n-1}$. How to continue from here on? Please verify my answer below if you are able to.


2 Answers 2


I guess I figured it out now. We can make a straight forward argument as follows:

$$\begin{align*}\frac{p_n}{p_{n-1}} = \frac{a_n*p_{n-1}}{p_{n-1}} + \frac{p_{n-2}}{p_{n-1}} = a_n + \frac{p_{n-2}}{p_{n-1}} = a_n + \frac{1}{\frac{p_{n-1}}{p_{n-2}}}. \end{align*}$$

Then $\frac{p_{n-1}}{p_{n-2}}=a_{n-1}+\frac{1}{\frac{p_{n-2}}{p_{n-3}}}$ and so on.

Continue doing this for arbitrary $n$ and get:

$$\frac{p_n}{p_{n-1}} =a_n + \frac{1}{a_{n-1} + \frac{1}{a_{n-2} + \frac{1}{\frac{p_{n-3}}{\ddots}}}} = [a_{n},a_{n-1},a_{n-2},\ldots,a_{0}].$$ Now $p_{n-1}q_{n}-p_nq_{n-1}=q_{n}^2-p_nq_{n-1}=(-1)^n$ by $\frac{p_n}{q_n}=\frac{p_n}{p_{n-1}}$ from what I stated earlier. Hence, $q^2\equiv(-1)^n$ mod $p$. $\Box$.


I think a bit more detail about the recursion is useful.

As noted in the answer by Guus Palmer, $$ \begin{align} \frac{p_n}{p_{n-1}} &=\left(a_n;\frac{p_{n-1}}{p_{n-2}}\right)\\ &=\left(a_n;a_{n-1},\frac{p_{n-2}}{p_{n-3}}\right)\\ &=\left(a_n;a_{n-1},a_{n-2},\dots,a_1,\color{#C00}{\frac{p_0}{p_{-1}}}\right)\\[6pt] &=\left(a_n;a_{n-1},a_{n-2},\dots,a_1,\color{#C00}{a_0}\right)\tag1 \end{align} $$ $$ %\begin{align} \frac{p_n}{p_{n-1}} &=a_n+\cfrac1{\frac{p_{n-1}}{p_{n-2}}}\\ &=a_n+\cfrac1{a_{n-1}+\cfrac1{\frac{p_{n-2}}{p_{n-3}}}}\\ &\,\,\vdots\\ &=a_n+\cfrac1{a_{n-1}+\cfrac1{a_{n-2}+\cfrac1{\begin{matrix}\ddots&\lower{18pt}{a_1+\cfrac1{\color{#C00}{\frac{p_0}{p_{-1}}}}}\end{matrix}}}}\\ &=a_n+\cfrac1{a_{n-1}+\cfrac1{a_{n-2}+\cfrac1{\begin{matrix}\ddots&\lower{18pt}{a_1+\cfrac1{\color{#C00}{a_0}}}\end{matrix}}}}\\ \end{align} $$

Since $p_{-2}=0$ and $p_{-1}=1$ in the standard recursion.

However, note that the sequence of denominators also follows the same initial recursion: $$ \begin{align} \frac{q_n}{q_{n-1}} &=\left(a_n;\frac{q_{n-1}}{q_{n-2}}\right)\\ &=\left(a_n;a_{n-1},\frac{q_{n-2}}{q_{n-3}}\right)\\ &=\left(a_n;a_{n-1},a_{n-2},\dots,a_2,\color{#C00}{\frac{q_1}{q_0}}\right)\\[6pt] &=\left(a_n;a_{n-1},a_{n-2},\dots,a_2,\color{#C00}{a_1}\right)\tag2 \end{align} $$ $$ %\begin{align} \frac{q_n}{q_{n-1}} &=a_n+\cfrac1{\frac{q_{n-1}}{q_{n-2}}}\\ &=a_n+\cfrac1{a_{n-1}+\cfrac1{\frac{q_{n-2}}{q_{n-3}}}}\\ &\,\,\vdots\\ &=a_n+\cfrac1{a_{n-1}+\cfrac1{a_{n-2}+\cfrac1{\begin{matrix}\ddots&\lower{18pt}{a_2+\cfrac1{\color{#C00}{\frac{q_1}{q_0}}}}\end{matrix}}}}\\ &=a_n+\cfrac1{a_{n-1}+\cfrac1{a_{n-2}+\cfrac1{\begin{matrix}\ddots&\lower{18pt}{a_2+\cfrac1{\color{#C00}{a_1}}}\end{matrix}}}}\\ \end{align} $$

Since $q_{-2}=1$ and $q_{-1}=0$ in the standard recursion, we cannot extend the continued fraction to include $\frac{q_0}{q_{-1}}$ as we did with $\frac{p_n}{p_{n-1}}$.

So we need to be careful about considering the beginning of the continued fraction without being careful of the ending terms. Although the later terms are less significant, in this case, they are important.

The rest of the answer is fine. For sequential approximants of any continued fraction, we have $$ p_{k-1}q_k-p_kq_{k-1}=(-1)^k\tag3 $$ Since $$ \frac{p_n}{q_n}=(a_0;a_1,a_2,\dots,a_{n-1},a_n)\tag4 $$ is a palindromic continued fraction, we have from $(1)$ and $(4)$ $$ \frac{p_n}{q_n}=\frac{p_n}{p_{n-1}}\tag5 $$ and applying $(5)$ to $(3)$, with $k=n$, we get $$ q_n^2-p_nq_{n-1}=(-1)^n\tag6 $$ That is, $$ q_n^2\equiv(-1)^n\pmod{p_n}\tag7 $$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .