Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.