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

2 Answers 2

0

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

  • 0
    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?2012-11-21
  • 0
    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}\,$...2012-11-21
  • 0
    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 ?2012-11-21
  • 0
    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 ?2012-11-21
  • 0
    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\,$2012-11-21
  • 0
    Yes right, but the problem is about an integer x (x < c), not any real x. How do we overcome that ?2012-11-21
  • 0
    I am trying to understand what's not clear to you but I can't succeed: as seen, $\,x\,$ is a function of that depends on given $\,a,b,c\in\Bbb N\,\,,\,c>b\,$, and it equals also a function of $\,k\,$, as seen above. We already know what the minimal value is obtained by this function, so...??2012-11-21
  • 0
    For instance, if we take k= 1, and we have a = 2, c=21, b = 1, we get x = 20/3 which is not an integer. We are looking for the smallest integer x. So k must be such that x is an integer.2012-11-21
  • 0
    Then take the minimal $\,k\,$ such that the expression is an integer...if it exists, otherwise the problem has no solution.2012-11-21
  • 0
    Yes. Correct. My question was infact about some idea to get to that value k in a quicker way (if it exists), without having to test them one by one starting from 1 and up. I was hoping in some sort of quick search or, more magically, some direct formula to get the k.2012-11-21
  • 0
    Very helpful discussion: at least i can imagine i am not missing something very obvious. Just let me know in case of any bright idea (to avoid the full search).2012-11-21
0

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.