If $\alpha$ and $\beta$ are two real numbers, we say that $\beta$ is equivalent to $\alpha$ if there are integers $a$, $b$, $c$, and $d$ such that $ad-bc=\pm1$ and $\beta=\frac{a\alpha+b}{c\alpha+d}$.

How can I show that two irrational numbers $\alpha$ and $\beta$ are equivalent if the tails of their simple continued fractions agree, that is, if

$$\begin{align} \alpha&=[a_0;a_1,a_2,\dots,a_j,c_1,c_2,c_3,\cdots]\\ \beta&=[b_0;b_1,b_2,\dots,b_k,c_1,c_2,c_3,\dots] \end{align}$$

where $a_i$, $i=0,1,2,\dots,j$; $b_i$, $i=0,1,2,\dots,k$; and $c_1$, $i=1,2,3,\dots$ are integers, all positive except perhaps $a_0$ and $b_0$?

This is what I tried: I assumed the above and tried to show that there exist $a$, $b$, $c$, and $d$ such that $ad-bc=\pm1$ and

$$\begin{align} \beta&=\frac{a\alpha+b}{c\alpha+d}\\ \Longrightarrow b_0+\frac{1}{b_1+\frac{1}{b_2+\cdots}}&=\frac{a\left(a_0+\frac{1}{a_1+\frac{1}{a_2+\cdots}}\right)+b}{c\left(a_0+\frac{1}{a_1+\frac{1}{a_2+\cdots}}\right)+d} \end{align}$$

However, the operations on the fractions are confusing, and I have the feeling that algebraic manipulations will not help or that there may be an easier way to tackle this problem.

  • 2
    $\begingroup$ Hint: Show that $[a_1,a_2,...]$ is equivalent to $[a_2,a_3,...]$. Then show that this equivalence is indeed an equivalence relationship, so $[a_1,a_2,...,a_n,c_1,...]$ is equivalent to $[a_2,...,a_n,c_1,...]$ which is equivalent to $[a_3,...,a_n,c_1,...]$ ... is equvalent to $[c_1,...]$. So $[a_1,...,a_n,c_1,...]$ is equivalent to $[c_1,...]$ is equivalent to $[b_1,...,b_k,c_1,...]$. $\endgroup$ – Thomas Andrews Apr 18 '12 at 15:23

Hint $\ $ This - like many properties of continued fractions - is clearer when continued fractions are viewed as sequences of Möbius maps. For an introduction to the Möbius viewpoint see the following exposition: A. Beardon, Continued Fractions, Discrete Groups and Complex Dynamics.

| cite | improve this answer | |

Proceed by induction on the number of terms after which they agree.

Base Case: Agree after $0$ terms. Then $\alpha = \beta = [c_1, c_2, \cdots ] $ and so $\alpha $ is equivalent to $ \beta$ (by your previous question).

Induction hypothesis: Suppose that if $ \alpha = [a_1, a_2, \cdots, a_n, c_1, c_2, \cdots] $ and $ \beta = [b_1, b_2, \cdots, b_n, c_1, c_2, \cdots ]$ then $\beta = \frac{ a \alpha + b}{c\alpha + d}$ for some integers $a,b,c,d$ such that $ad-bc = \pm 1.$

Induction step:

Let $ \alpha = [a_0, a_1, a_2, \cdots, a_n, c_1, c_2, \cdots] $ and $ \beta = [b_0, b_1, b_2, \cdots, b_n, c_1, c_2, \cdots ].$

Then $\alpha = a_0 + \frac{1}{\alpha'} $ and $\beta = b_0 + \frac{1}{\beta'}$ where (by the Induction hypothesis) $\alpha'$ is equivalent to $\beta'.$

Thus $ \frac{1}{\alpha - a_0} $ is equivalent to $ \frac{1}{\beta - b_0} $ so there exists $a,b,c,d$ with $ad-bc=\pm 1$ such that $$ \frac{1}{\alpha -a_0} = \frac{ \frac{a}{\beta - b_0} + b}{ \frac{c}{\beta- b_0} + d} .$$

Multiply top and bottom of the fraction by $\beta - b_0$: $$ \frac{1}{\alpha - a_0} = \frac{a+b\beta - bb_0}{c+d\beta-db_0} $$ so solving for $\alpha$: $$\alpha = \frac{c+d\beta-db_0}{a+b\beta-bb_0} + a_0 = \frac{c+d\beta-db_0+ aa_0+a_0b\beta-a_0bb_0}{a+b\beta-bb_0} $$

$$= \frac{ (a_0b+d)\beta + (aa_0+a_0bb_0-db_0+c) }{b\beta + (a-bb_0)} .$$

Now since $$(a-bb_0)(a_0b+d) - b(aa_0+a_0bb_0-db_0+c) = ad - bc =\pm 1$$

we have that $\alpha$ is equivalent to $\beta$ as desired.

| cite | improve this answer | |
  • $\begingroup$ That makes a whole lot of sense! But I have one question: I suppose $\alpha$ and $\beta$ having different indexes ($a_j$ and $b_k$, respectively) does not really affect the induction step? $\endgroup$ – wjm Apr 18 '12 at 16:19
  • $\begingroup$ @JosuéMolina You've found a flaw in my proof! I didn't read the question well enough, I thought $j=k.$ I'll try to fix it, in the meanwhile you should unaccept my answer and read into Thomas' hint. $\endgroup$ – Ragib Zaman Apr 18 '12 at 16:23
  • $\begingroup$ @JosuéMolina I realized the best way is to use Thomas' hint, I was rewriting my answer employing his hint but it got deleted when I was just about finished, which has demoralized me. Try your best to use his hint and if you can not, edit your post stating what step you run into troubles in. $\endgroup$ – Ragib Zaman Apr 18 '12 at 16:43
  • $\begingroup$ @RagibZaman : I think this question is worth up-voting; I'm the only one who's done that so far. $\endgroup$ – Michael Hardy Apr 18 '12 at 18:12
  • $\begingroup$ @Michael, I think it's a standard exercise in intro Number Theory, and thus not worth up-voting (by me - I'm not trying to influence anyone else). $\endgroup$ – Gerry Myerson Apr 18 '12 at 23:54

I did what Thomas Andrews suggested and obtained this:

Let $x_1=[a_0;a_1,a_2,\dots]$ and $x_2=[a_1;a_2,a_3,\dots]$. Then

$$x_1=a_0+\frac{1}{x_2}=\frac{a_0x_2+1}{x_2}=\frac{a_0\cdot x_2+1}{1\cdot x_2+0}.$$

Therefore, $a=a_0$, $b=1$, $c=1$, and $d=0$;


and $x_1$ is equivalent to $x_2$.

Now it is just a matter of using this to finish up the proof.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.