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



Length of Hirzebruch continued fractions
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](http://iam.khv.ru/articles/Ustinov/nth15_eng.pdf) 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).
$$


