應用：夾在中間的分數

想法：把分數倒過來

首先，如果存在一個整數 \(k\) 使得 \(\frac{a}{b} < k < \frac{c}{d}\)，那麼顯然答案就是 \(\frac{p}{q} = \frac{k}{1}\)。 假設現在 \(\frac{a}{b}\) 與 \(\frac{c}{d}\) 同時介於某兩個連續整數之間，比方說 \(\frac{a}{b},\frac{c}{d} \in [k, k+1]\)，那麼我們可以將它們同時減去 \(k\)，這並不影響我們要找的分數的最小分母的性質。

\[ \frac{a-kb}{b} < \frac{p-kq}{q} < \frac{c-kd}{d} \]

現在假設兩個分數都不超過 \(1\)，即 \(\frac{a}{b}, \frac{c}{d} \le 1\)。那麼我們可以同時將兩個數字「反過來」，變成下面這樣：

\[ \frac{b}{a} > \frac{q}{p} > \frac{d}{c} \ge 1 \]

就可以套用輾轉相除法的想法，重複前述之步驟啦～

關於正確性

至於這個方法的正確性，也能夠使用數學歸納法來證明之。 前面的想法提及了三個情形：兩數中間夾了整數、兩數皆至少為 \(1\)、兩數皆小於 \(1\)。 第一種情形可以視為 base case，另外兩種情形就可以用『分子加分母』的值進行歸納。 需要注意的是，由於會將分子與分母顛倒，所以我們需要證明當分母是最小值的時候，分子也同時會是所有解裡頭最小的分子值。 （下略五百字）