Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}}}.$$

share|improve this question
1  
Sometimes known as the "negative-regular continued fraction". –  Gerry Myerson Nov 3 '12 at 4:28
    
Is there, by any chance, a pun on Kettenbruch? –  Alain Valette Nov 3 '12 at 7:16
3  
@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 ;) –  quid Nov 3 '12 at 11:09
2  
@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$. –  Liviu Nicolaescu Nov 5 '12 at 10:18
1  
According to Perron (Vol. 1, $\S$ 43) this fraction as known as ``reduced regular continued fraction'' (reduziert-regelmaessige Kettenbrueche). –  Alexey Ustinov Nov 6 '12 at 1:35

2 Answers 2

up vote 9 down vote accepted

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). $$

share|improve this answer
    
Thanks, this is very useful, and definitely the kind of argument I was looking for. –  Gjergji Zaimi Nov 7 '12 at 8:33
    
Will it give anything useful for toric geometry? –  Alexey Ustinov Nov 7 '12 at 9:33

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?

share|improve this answer
    
Yes, there was a crucial missing assumption, that $n > ab$. Thank you for pointing this out. –  Gjergji Zaimi Nov 5 '12 at 19:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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