For fixed $A$ and $B$ find $C$ and $D$ that $|\frac{A}{B}-\frac{C}{D}|$ is minimal

Question

We have $A$ and $B$.

$A/B$ - irreducible fraction.

You must find two natural numbers $C$ and $D$ that $|\frac{A}{B}-\frac{C}{D}|$ is minimal and $C/D$ - irreducible fraction. If there are multiple answers find $C$ and $D$ with the minimal $D$.

$0 < C < D < B$

$0 < A < B$

B > 2

$A$, $B$ - natural numbers.

Answer 1

Hint: Use the fact that $\gcd(A,B)=1$ to find $U,V\in\Bbb Z$ such that $UA+VB=1$.

Remark: The constraints sometimes prevent the existence of a solution. For example, $A=1$, $B=2$ satisfies $0<A<B$, but you cannot satisfy $0<C<D<B$. But there are also other strange cases where the hint above first produces a solution with $B\ge D$.