Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The last part means that $q_1 = d_1$, $q_2 = d_2 \cdot d_1$, $q_r = d_r \cdots d_2 \cdot d_1$. Consider an example $m=4$ and $n=5$. Then $d_1=d_2=2$ and $d_3 = 5$ is a solution. –  Sasha Oct 14 '11 at 16:23
1  
It looks like some sort of a constrained Egyptian fraction decomposition... –  J. M. Oct 14 '11 at 16:39

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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$. –  Arturo Magidin Oct 14 '11 at 16:32

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.