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
    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.