I have two quantities $(nb-x)/a$ and $nb/a$ and I need to find minimum value of $n$ given $a, b$ such that $\exists k\in\mathbb Z$ for which $(nb-x)/a\le k<nb/a$ or $nb-x\le ak\le nb$ or $nb\le x+ak<x+nb$ or $0\le ak<x\pmod b$. My initial thoughts were to use binary search but $f(x)=ak\pmod b$ will not be monotonic between $0$ and $b$. Can you give me a hint?
Update:
In other words given $x$, $a$ and $b$, find minimum $k$ such that $x+ak\equiv x'\pmod b$, example $x=5$, $a=7$, $b=15$, for $n=1$, $x'=12>x$, for $n=2$, $x'=4<x$. Hence the minimum required $n$ is $2$