Largest Fraction Smaller than a Given Fraction

Question

Suppose that we have a fraction $\frac ab$ where $a$ and $b$ are mutually prime positive integers. What is the largest fraction $\frac cd$ where $c$ and $d$ are mutually prime positive integers such that $\frac cd < \frac ab$ and $c \le a$ ?

Answer 1

Turns out this always works. The fraction you want is the positive integers $c,d$ such that $c \leq a$ and $$ ad - bc = 1. $$ First, there is such a pair. I am taking $a > 1, b > 1.$ The penultimate convergent $x/y$ in the continued fraction for $a/b$ solves $x < a, y < b,$ and either $ay-bx = 1$ or $ay-bx = -1.$ In the first case we have it, take $c=x, d=y.$ ADDED: recall that continued fraction convergents are alternately above and below the final value. In the other case, we have $a(-y) - b(-x) = 1,$ so $a(b-y) -b(a-x) = 1 \; ; \;$ in this case, we actually had $\frac{x}{y} > \frac{a}{b},$ clearly unsuitable as it stands. This was the case in comment below with $\frac{3}{2} > \frac{7}{5} \; .$

Next, Lemma 2.6 on page 13 of Edward B. Burger, Exploring the Number Jungle says: Let $\frac{p}{q} < \frac{r}{s}$ be two rational number satisfying $ps -rq = -1.$ Suppose that $a/b$ is a rational number satisfying $\frac{p}{q} \leq \frac{a}{b} \leq \frac{r}{s}.$ Then there exist nonnegative integers $\lambda$ and $\mu$ such that $$ a = \lambda p + \mu r \; , \; \; \mbox{and} \; \; \; b = \lambda q + \mu s \; \; . $$ Proof: take $$ \lambda = br - as \; , \; \; \mu = a q - b p . $$ Note that, if we have the stronger $\frac{p}{q} < \frac{a}{b} < \frac{r}{s},$ we actually get $ \lambda, \mu \geq 1. $

Back to our original letters, with $ ad - bc = 1, $ if $e/f$ is a rational number strictly between them, then $e > a.$

experiments

Mon Apr 30 17:46:51 PDT 2018
     a     b     c     d       a d - b c  
     1     2     1     3           1
     2     1     1     1           1
     1     3     1     4           1
     3     1     2     1           1
     1     4     1     5           1
     2     3     1     2           1
     3     2     1     1           1
     4     1     3     1           1
     1     5     1     6           1
     5     1     4     1           1
     1     6     1     7           1
     2     5     1     3           1
     3     4     2     3           1
     4     3     1     1           1
     5     2     2     1           1
     6     1     5     1           1
     1     7     1     8           1
     3     5     1     2           1
     5     3     3     2           1
     7     1     6     1           1
     1     8     1     9           1
     2     7     1     4           1
     4     5     3     4           1
     5     4     1     1           1
     7     2     3     1           1
     8     1     7     1           1
     1     9     1    10           1
     3     7     2     5           1
     7     3     2     1           1
     9     1     8     1           1
     1    10     1    11           1
     2     9     1     5           1
     3     8     1     3           1
     4     7     1     2           1
     5     6     4     5           1
     6     5     1     1           1
     7     4     5     3           1
     8     3     5     2           1
     9     2     4     1           1
    10     1     9     1           1
     1    11     1    12           1
     5     7     2     3           1
     7     5     4     3           1
    11     1    10     1           1
     1    12     1    13           1
     2    11     1     6           1
     3    10     2     7           1
     4     9     3     7           1
     5     8     3     5           1
     6     7     5     6           1
     7     6     1     1           1
     8     5     3     2           1
     9     4     2     1           1
    10     3     3     1           1
    11     2     5     1           1
    12     1    11     1           1
     1    13     1    14           1
     3    11     1     4           1
     5     9     1     2           1
     9     5     7     4           1
    11     3     7     2           1
    13     1    12     1           1
     1    14     1    15           1
     2    13     1     7           1
     4    11     1     3           1
     7     8     6     7           1
     8     7     1     1           1
    11     4     8     3           1
    13     2     6     1           1
    14     1    13     1           1
     1    15     1    16           1
     3    13     2     9           1
     5    11     4     9           1
     7     9     3     4           1
     9     7     5     4           1
    11     5     2     1           1
    13     3     4     1           1
    15     1    14     1           1
     1    16     1    17           1
     2    15     1     8           1
     3    14     1     5           1
     4    13     3    10           1
     5    12     2     5           1
     6    11     1     2           1
     7    10     2     3           1
     8     9     7     8           1
     9     8     1     1           1
    10     7     7     5           1
    11     6     9     5           1
    12     5     7     3           1
    13     4     3     1           1
    14     3     9     2           1
    15     2     7     1           1
    16     1    15     1           1
     1    17     1    18           1
     5    13     3     8           1
     7    11     5     8           1
    11     7     3     2           1
    13     5     5     2           1
    17     1    16     1           1
     1    18     1    19           1
     2    17     1     9           1
     3    16     2    11           1
     4    15     1     4           1
     5    14     1     3           1
     6    13     5    11           1
     7    12     4     7           1
     8    11     5     7           1
     9    10     8     9           1
    10     9     1     1           1
    11     8     4     3           1
    12     7     5     3           1
    13     6     2     1           1
    14     5    11     4           1
    15     4    11     3           1
    16     3     5     1           1
    17     2     8     1           1
    18     1    17     1           1
     1    19     1    20           1
     3    17     1     6           1
     7    13     1     2           1
     9    11     4     5           1
    11     9     6     5           1
    13     7    11     6           1
    17     3    11     2           1
    19     1    18     1           1