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.