# Solving an equation in modular arithmetic

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)]

-

$$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}$$

-
Thank you. This formulation seems to say that ax+b is a multiple (k times) of c−x. But how does it actually help finding the smallest x such that ... ? Am i missing something? –  Pam Nov 21 '12 at 11:33
Well, $\,ax+b=0\pmod{c-x}\,$ means exactly that: the left hand side is a multiple of $\,c-x\,$. About the minimal $\,x\,$ just try to minimize $\,\frac{kc-b}{a+k}\,$. For example, taking $\,k=1\,$ gives us $\,x=\frac{c-b}{a+1}\,$... –  DonAntonio Nov 21 '12 at 13:30
Yes, in terms of k, the question would be, how can i find k in such a way to get the smallest (integer) x ? I mean can i do that in some quicker way than brutally trying all possible values of k ? –  Pam Nov 21 '12 at 15:10
For instance, would it be possible to create something like a binary search, a Newton like iteration, or any other quick way to get k ? –  Pam Nov 21 '12 at 20:01
The function $$f(k)=\frac{kc-b}{a+k}$$ is monotone ascending according to the given data (why?), so the minimal value is assumed at $\,k=1\,$ –  DonAntonio Nov 21 '12 at 20:28
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.