1
$\begingroup$

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

$\endgroup$

2 Answers 2

0
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ 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? $\endgroup$
    – Pam
    Nov 21, 2012 at 11:33
  • $\begingroup$ 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}\,$... $\endgroup$
    – DonAntonio
    Nov 21, 2012 at 13:30
  • $\begingroup$ 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 ? $\endgroup$
    – Pam
    Nov 21, 2012 at 15:10
  • $\begingroup$ 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 ? $\endgroup$
    – Pam
    Nov 21, 2012 at 20:01
  • $\begingroup$ 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\,$ $\endgroup$
    – DonAntonio
    Nov 21, 2012 at 20:28
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .