Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\frac{a}{b}$ and $\frac{c}{d}$ be two reduced fractions with $bc-ad > 1$ (and hence $\frac{a}{b} \lt \frac{c}{d}$) and $a,b,c,d$ positive. It is well known that there are integers $u,v$ such that $0 \leq u \leq a, 0 \leq v \leq b$ and $av-bu=1$. Let $q$ be the largest positive below $\frac{ \max(b,d)+v}{b}$, i.e. the euclidean quotient of $\max(b,d)+v$ by $b$). Then the following inequality holds :

$$ cv-du \leq q(bc-ad) \tag{*} $$

I know that (*) is true, but the only proof I know relies on the heavy machinery of Farey sequences and the Stern-Brocot tree. Is there a more direct proof ?

share|cite|improve this question
I corrected the spelling of "Euclidean". An argument for a lower-case initial can be made, so I left that alone. But I thought of explaining why it's spelled that way. The spelling $\mathrm{EUK}\Lambda\mathrm{EI}\Delta\mathrm{H}\Sigma$ could be transcribed as "Euklides". If I'm not mistaken the final "-es" varies with the way the word is used in a sentence, and since the English language doesn't do that, English writers in about the 1500s dropped it. At this point language historians will jump in and tell me how my account is intolerably simple-minded. – Michael Hardy Mar 5 '12 at 16:27
....but the "-es" at the end could be considered as explaining it, just as "Archimedes" becomes "Archimedean", with a final "-ean". As often happens in modern Greek, the upsilon is pronounced like an "f" when it's followed by a "k" and in some other contexts. Googling, I was surprised to learn that the immortal geometer's name seems to be a commonplace surname in Greece today. See, for example. – Michael Hardy Mar 5 '12 at 16:30

Let $bc-ad=r$. Then $$bcv-avd=rv,\quad bcv-(1+bu)d=rv,\quad (cv-du)b=rv+d,\quad cv-du=(v/b)r+(d/b),\quad cv-du=(v/b)(bc-ad)+(d/b)$$ which is pretty close to what you want.

share|cite|improve this answer
Thanks for your partial answer Gerry, but "pretty close" is not enough. My thesis supervisor would ask, "How's your proof of result X going?" "I completed 99% of it." "Noticed how the last 1% is always the hardest part ?" – Ewan Delanoy Mar 6 '12 at 9:49
Yes, but you are not my thesis supervisor. – Gerry Myerson Mar 6 '12 at 11:44

Your Answer


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.