# Rational with minimal denominator between two rationals [duplicate]

My question from an easy problem.

$$p,q$$ are positive integers such that $$\frac{5}{9}<\frac{p}{q}<\frac{4}{7}$$ find $$p,q$$ such that $$q$$ is the smallest number that satisfies this inequality.

Draw the line of $$y<\frac{9}{5}x$$ and $$y>\frac{7}{4}x$$ , we can "observe" that $$\frac{9}{16}$$ is such number.

However, if the question becomes

$$a,b,c,d$$ are positive integers such that $$\frac{a}{c}<\frac{b}{d}$$ find $$p$$,$$q$$ such that $$q$$ is the smallest number that satisfies the inequality

$$\frac{a}{c}<\frac{p}{q}<\frac{b}{d}$$

• now try denominators from 2 to 15. – Will Jagy Oct 20 at 13:48
• $\frac59\lt\frac pq\lt\frac47$ is not an equation. An equation has an $=$ sign in it. – bof Oct 20 at 14:00
• Those who are familiar with Farey Sequences will solve this immediately. If $a,b,c,d\in \Bbb Z^+$ with $a/b<c/d$ and $***\; (bc-ad)=1 \; ***\;$ then every $x\in \Bbb Q\cap (a/b,c/d)$ is expressed in lowest terms as $x=(ma+nc)/(mb+nd)$ for unique $m,n \in \Bbb Z^+.$ So $mb+nd\ge b+d,$ with equality iff $m=n=1.$ So in the Q, $p/q=(5+4)/(9+7)=9/16.$ – DanielWainfleet Oct 20 at 14:23
• @DanielWainfleet great! Farey sequence can perfectly be applied to this question. Did not spot that before lol. – camhunter Oct 20 at 14:29
• @camhunter I think you'll find it's the same solution. – Matthew Daly Oct 20 at 15:05

What do we get with continued fractions?

$$\dfrac{5}{9}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{4}}}$$

$$\dfrac{4}{7}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3}}}$$

The fractions are identical until we get to the last layer where one has a $$4$$ and the other has a $$3$$. Were there an integer between $$3$$ and $$4$$ we could replace the last layer with the smallest such integer, following the accepted answer here.

We don't have such an integer between $$3$$ and $$4$$ so this does not appear to work. But we can force the issue by rendering

$$4=3+\dfrac{1}{1}$$

$$3=3+\dfrac{1}{M}$$

where $$M$$ is taken as approaching infinity. Then we have

$$\dfrac{5}{9}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{1}}}}$$

$$\dfrac{4}{7}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{M}}}}$$

Now we put $$2$$ as the smallest integer between $$1$$ and $$M$$ to get an intervening fraction with a minimal denominator. Thus

$$\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{2}}}}=\dfrac{9}{16}$$

• Thanks! This is a brilliant method! – camhunter Oct 20 at 14:27
• Apparently not brilliant enough for some people. – Oscar Lanzi Nov 7 at 15:01