10
$\begingroup$

Suppose $a,b$ are two natural numbers relatively prime to $n$ and to each other. Assume $n\geq ab+1$. Suppose further that $\frac{a}{b}\equiv k \pmod{n}$ for some $k\in \lbrace 1,2,\dots, n-1\rbrace$ and $\frac{a}{b}\equiv k'\pmod{n+ab}$ for some $k'\in \lbrace 1,2,\dots, n+ab-1\rbrace$.

Question: Is there an elementary proof that the length of the continued fraction of $\frac{n}{k}$ is equal to the length of the continued fraction of $\frac{n+ab}{k'}$?

This came out of a broader result, and for this particular case I can prove it using routine toric geometry, however I would like to know of some elementary tricks to deal with continued fractions.


Here by continued fraction I mean the Hirzebruch continued fraction $$\frac{n}{k}=a_0-\frac{1}{a_1-\frac{1}{a_2-\cdots}}.$$ For example, when $a=2, b=3$ and $n=17$, we get $k=12$ and $k'=16$, so the fractions are $$\frac{17}{12}=2-\frac{1}{2-\frac{1}{4-\frac{1}{2}}}\qquad and \qquad\frac{23}{16}=2-\frac{1}{2-\frac{1}{5-\frac{1}{2}}}.$$

$\endgroup$
8
  • 2
    $\begingroup$ Sometimes known as the "negative-regular continued fraction". $\endgroup$ Nov 3, 2012 at 4:28
  • $\begingroup$ Is there, by any chance, a pun on Kettenbruch? $\endgroup$ Nov 3, 2012 at 7:16
  • 4
    $\begingroup$ @Alain Valette: I am not sure if you mean something more specific, but the Hirzebruch is the mathematician, as he conisdererd them somewhere, sometimes also the name Jung is mentioned in addition. So one finds say Hirzebruch-Jung-Kettenbruch in German texts. I could envision somebody coming along and calling it (or rather the plural) Hirzebrüche as a pun; I found nothing googling for this. But, the next person doing so might ;) $\endgroup$
    – user9072
    Nov 3, 2012 at 11:09
  • 2
    $\begingroup$ @Gjergji: Your "routine toric geometry" line brought a smile to my face. I suppose you could try to convert the routine geometry facts into statements on the geometry of numbers. As far as I can remember the length of the Hirzebruch-Jung continued fraction is related to the number of edges in a Newton polygon, the convex hall of the nonzero lattice points in side the angle determined by the positive horizontal semi-axis and the ray of slope $a/b$. $\endgroup$ Nov 5, 2012 at 10:18
  • 1
    $\begingroup$ According to Perron (Vol. 1, $\S$ 43) this fraction as known as ``reduced regular continued fraction'' (reduziert-regelmaessige Kettenbrueche). $\endgroup$ Nov 6, 2012 at 1:35

2 Answers 2

10
$\begingroup$

Lets call expansions $$\langle x_1,\ldots,x_m\rangle:=\cfrac{1}{x_1-{\atop\ddots\,\displaystyle{-\cfrac{1}{x_m}}}}$$ (as in Perron's book) reduced regular continued fractions (RRCF). Probably they are older then Hirzebruch.

We'll prove more precise statement.

Theorem. If $(n,ab)=1$ and $n>ab$ then RRCF for all numbers $$\left\{\frac{ab^{-1}\pmod{(n+kab)}}{n+kab}\right\}\qquad(k\ge 0)$$ are almost equal: they have equal length and differ only in one partial quotient.

Remark 1. Common factors of $a$ and $b$ can be moved into $k$. If $d=(a,b)$, $a=da_1$, $b=db_1$, then \begin{gather*} \left\{ \frac{ab^{-1}\pmod{(n+kab)}}{n+kab}\right\} =\left\{ \frac{a_1b_1^{-1}\pmod{(n+kab)}}{n+kab}\right\} \\=\left\{ \frac{a_1b_1^{-1}\pmod{(n+(kd^2)a_1b_1)}}{n+(kd^2)a_1b_1}\right\}. \end{gather*} So we can assume that $(a,b)=1$.

Remark 2. The proof will be given in terms of modified continuants $K(x_1,\ldots, x_n)$ (see ``Concrete Mathematics'' for more explanations). These polynomials are defined by initial conditions $$K()=1,\quad K(x_1)=x_1$$ and the following recurrence: $$K(x_1,\ldots, x_n)=x_nK(x_1,\ldots, x_{n-1})-K(x_1,\ldots, x_{n-2})\qquad(n\ge2).$$ (In the usual definition minus must be replaced by plus.) For convenience $K_{-1}:=0$ (empty RRCF is $0$).

In terms of continuants RRCF can be written as $$\langle x_1,\ldots,x_n\rangle=\frac{K(x_2,\ldots, x_n)}{K(x_1,\ldots, x_n)}.$$

Continuant's properties. All these properties can be proved by induction (or from ``Euler’s rule'').

1$^{\circ}.$ $K(x_1,\ldots, x_n)=K(x_n,\ldots, x_{1})$.

2$^{\circ}.$ \begin{gather*} K(x_1,\ldots, x_n,x_{n+1}, \ldots, x_{m+n})\\=K(x_1,\ldots, x_n)K(x_{n+1}, \ldots, x_{m+n})-K(x_1,\ldots, x_{n-1})K(x_{n+2}, \ldots, x_{m+n}) \end{gather*}

3$^{\circ}.$ $\begin{vmatrix} K(x_2,\ldots, x_{n-1})&K(x_2,\ldots, x_n) \\ K(x_1,\ldots, x_{n-1})&K(x_1,\ldots, x_n) \end{vmatrix}=-1$. In particular if $$\frac{A}{a}=\left<r_1, \ldots, r_v\right>=\frac{K(r_2, \ldots, r_v)}{K(r_1, \ldots, r_v)}$$ then $$K(r_1, \ldots, r_{v-1})=A^{-1}\pmod{a},\qquad K(r_2, \ldots, r_{v-1})=\frac{AA^{-1}\pmod{a}-1}{a}.$$

4$^{\circ}.$ Euler's identity (see A Short Proof of Euler's Identity for Continuants for additional arguments). (2$^{\circ}$ and 3$^{\circ}$ are special cases of this identity) $$ K(x_1, \ldots, x_{m+n})K(x_{m+1}, \ldots, x_{m+l})-K(x_1, \ldots, x_{m+l})K(x_{m+1}, \ldots, x_{m+n})$$ $$+K(x_1, \ldots, x_{m-1})K(x_{m+l+2}, \ldots, x_{m+n})=0. $$

Proof of the Theorem. For a given $n$ define $a^{-1}:=a^{-1}\pmod{n}$, $b^{-1}:=b^{-1}\pmod{n}$, $0\le a,b\le n-1$ (inverse number is always least possible nonnegative) and $t_a$, $t_b$ such that $aa^{-1}=1+t_an$, $bb^{-1}=1+t_bn$. Let $$ \frac{A}{a}=\left\{\frac{bt_a}{a}\right\}=\left<r_1, \ldots, r_v\right>,\qquad A^{-1}:=A^{-1}\pmod{a};$$ $$\frac{B}{b}=\left\{\frac{at_b}{b}\right\}=\left<q_1, \ldots, q_u\right>,\qquad B^{-1}:=B^{-1}\pmod{b};$$ $$\frac{P(x)}{Q(x)}=\left<q_1, \ldots, q_u,x,r_v, \ldots, r_1\right>. $$ By 2$^{\circ}$, 3$^{\circ}$ and main recurrence $$ Q(x)=K(q_1, \ldots, q_u,x,r_v, \ldots, r_1)=$$ $$xK(q_1, \ldots, q_u)K(r_v, \ldots, r_1)-K(q_1, \ldots, q_{u-1})K(r_v, \ldots, r_1)-K(q_1, \ldots, q_u)K(r_{v-1}, \ldots, r_1)$$ $$=xab-aB^{-1}-bA^{-1}. $$ Hence $$ Q(x)\equiv -bA^{-1}\equiv -b((bt_a)^{-1}\pmod{a})\equiv -t_a^{-1}\equiv n\pmod{a},$$ $$Q(x)\equiv -aB^{-1}\equiv -a((at_b)^{-1}\pmod{b})\equiv -t_b^{-1}\equiv n\pmod{b}.$$ Therefore $$Q(x)\equiv n\pmod{ab},$$ and for some integer $x_0$ we have $Q(x_0)=n$. We know that $n>ab$. It means that $$x_0ab-aB^{-1}-bA^{-1}>ab,$$ so $x_0\ge 2$ and $\left<q_1, \ldots, q_u,x_0,r_v, \ldots, r_1\right>$ is really RRCF. Choosing arbitrary $x=x_0+k$ we'll get progression $n+kab$ as in the statement of the theorem.

Let's check the numerator $P(x)$. Final step $P(x)\equiv ab^{-1}\pmod{Q(x)}$ follows from identity $$bP(x)-BQ(x)=a,$$ which is a special case of Euler's identity. Nevertheless this identity can be verified directly with help of 1$^{\circ}$--3$^{\circ}$: $$ P(x)=K(q_2, \ldots, q_u,x,r_v, \ldots, r_1)=$$ $$xK(q_2, \ldots, q_u)K(r_v, \ldots, r_1)-K(q_2, \ldots, q_{u-1})K(r_v, \ldots, r_1)-K(q_2, \ldots, q_u)K(r_{v-1}, \ldots, r_1)$$ $$=xaB-a\frac{BB^{-1}-1}{b}-BA^{-1},$$ $$ bP(x)-a=B(xab-aB^{-1}-bA^{-1})=BQ(x). $$

$\endgroup$
3
  • $\begingroup$ Thanks, this is very useful, and definitely the kind of argument I was looking for. $\endgroup$ Nov 7, 2012 at 8:33
  • 1
    $\begingroup$ Will it give anything useful for toric geometry? $\endgroup$ Nov 7, 2012 at 9:33
  • 2
    $\begingroup$ This answer was published as a short note "On continued fractions of equal length" at mathnet.ru/php/… $\endgroup$ Mar 18, 2015 at 2:43
4
$\begingroup$

Forgive me, this should be in the comments, but I am still building my reputation up to comment. If a=5, b=4, n=7, then k=3, k'=8, and n+ab=27.

Here, $\frac{n}{k}=\frac{7}{3}=3-\frac{1}{2-\frac{1}{2}}$ but $\frac{n+ab}{k'}=\frac{27}{8}=4-\frac{1}{2-\frac{1}{3-\frac{1}{2}}}$. Am I missing something or is there a further assumption on these numbers?

$\endgroup$
1
  • $\begingroup$ Yes, there was a crucial missing assumption, that $n > ab$. Thank you for pointing this out. $\endgroup$ Nov 5, 2012 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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