4
$\begingroup$

Help me please to understand this exercise and probably to solve it.

Show that every positive rational number $\frac{m}{n}\in (0,1)$ can be represented as $\frac{m}{n} = \frac{1}{q_1} + \frac{1}{q_2} + \cdots + \frac{1}{q_r},$ where $q_1 \lt q_2\lt \cdots \lt q_r$ are positive integers and $q_i$ is a divisor of $q_{i+1}$ for all $i=1,2,\ldots,r-1$.

I don't get the last part? Tja, actually, I don't know in general how to solve it.

  • 1
    It looks like so$m$e sort of a co$n$strained Egyptian fraction decomposition...2011-10-14

1 Answers 1

7

Find the least integer $q_1$ with

$\frac mn\ge\frac1{q_1}\tag1$

and write

$\frac mn=\frac1{q_1}(1+x)\;.$

Solving for $x$ yields

$x=\frac{q_1m-n}n\;.$

By $(1)$, we have $x\ge0$. Since $q_1$ is the least number for which $(1)$ holds, we also have

$\frac mn\lt\frac1{q_1-1}\;,$

which yields

$q_1m-n\lt m$

and thus

$x\lt\frac mn\lt1\;.$

Thus we have $x\in[0,1)$. If we slightly generalize to include $0$ in the interval (with $r=0$), the result follows by induction: $x$ has the same denominator as $m/n$ but a lower numerator, so if we apply the same procedure to $x$ recursively, the recursion must eventually end; then substituting the results and multiplying out all the parentheses yields the desired representation.

  • 0
    Just to add: The "induction" we are doing is a kind of "bounded" induction: we *fix* $n$, and we do induction on $m$, but only need to worry about $1\leq m\lt n$.2011-10-14