Given $A, B, C$ positive integers, $B < C,$
I would like some thoughts about (possibly efficient) ways to find the smallest integer $X$, where $0 < X < C$, such that:
$$A X + B \pmod{C - X} = 0$$
($u \pmod{ w}$ denotes the remainder of the division $u/w$)
Any pointers to similar equations? Where should I be looking? [Some iterative method would also be fine (provided not a brute search)]
On
This is not a solution, but rather an exploration.
Consider a $x$ and $k$ which satisfy:- $$ ax+b = k(c-x) $$ and let us take a look at what value $y=c-x$ would take:- $$ a(c-y)+b = ky $$ $$ ac-ay+b=ky $$ $$ac+b=ky+ay$$ $$ac+b=(k+a)y$$ We know $a$, $b$ and $c$ so we can compute the value that $(k+a)y$ must take. If it is prime, then clearly we are in trouble! Otherwise we can pick any factorisation $QR = ac+b$, and let $y=Q$ provided that $R>a$. Since we want $x$ to be as small as possible, we naturally want $y$ to be as large as possible. Of course this still leaves the problem of finding suitable factorisations which may well be more expensive then trying each value for $x$ in the first place.
$$ax+b=0\pmod{c-x}\Longleftrightarrow ax+b=k(c-x)=kc-kx\Longleftrightarrow$$
$$(a+k)x=kc-b\Longleftrightarrow x=\frac{kc-b}{a+k}$$