Find the smallest $k$ such that $kx bmod n in [a,b]$

Problem: For given $x, a, b$ all reduced mod $n$, find the smallest non-zero $k$ (if any) such that $kx bmod n in [a, b]$. The prime factorization of $n$ is known.

So far I’ve found a plausible solution for the simpler problem $kx bmod n le b$ where $x^{-1}$ exists:

If $b$ is small, one can simply enumerate solutions: For each $y le b$, compute $yx^{-1} bmod n = k$. It becomes clear that the answer is dependent on the ratio $f = frac{x^{-1}}n$. If $b = 2$, then $y = 2$ if $f > frac12$. For $b = 3$, $y = 3$ if $f in [frac13,frac12)cup[frac23,1)$, falling back to the previous case(s) otherwise. For $b = 4$, $y = 4$ if $f in [frac14,frac13)cup[frac34,1)$.

In each case, $y$ is the denominator of the largest fraction $le f$ such that $y le b$. This can be found using a Stern–Brocot tree, moving up the tree until we find a satisfactory value.

But I’ve been unable to extend this result to the arbitrary interval above.