How can I find $x$ such that $ax \equiv 1 \pmod{bx+c}$, given $a,b,c$?

Question

Everything I've read about modular arithmetic generally concerns doing things in some "mod m" world where "m" is some constant. But I'm perplexed how to tackle modular arithmetic problems where the aim is to find the modulus which produces some result.

More specifically: "Given positive integers $a,b,c$, how can I go about efficiently finding $x$ such that $ax \equiv 1 \pmod{bx+c}$?"

For example, with $a=2021$, $b=89$, $c=1932$, I'm looking for $x$ such that $2021x \equiv 1 \pmod{89x+1932}$. By brute force search, I happen to know that this is solved by $x=83$, but surely there's a better way...

For what it's worth, in the problems I'm concerned with $c=a-b$ (as hinted by the example numbers given above), but I'm not sure how useful that is if there's a more general technique anyway.

Answer 1

Hint: Since $a,b,c,x \in \Bbb{N}$ $$ax \equiv 1 \mod bx+c\Rightarrow ax=(bx+c)y+1\Rightarrow x=\frac{cy+1}{a-by}\in \Bbb{N} \Rightarrow a-by \gt 0 \\ \Rightarrow 0 \le y \le \lfloor\frac{a}{b}\rfloor$$ so you're searching for $y$ in a bounded set...With no further information about $a,b,c$ you have to make the computer search for $y$ in this set, as brute force would be the only possibility..

Answer 2

Hint $ $ Completing the product (rectangle) yields $$\begin{align} ax - 1 &= (bx+c)y\\[.2em] \iff (bx+c)(a-by) &= ac+b\end{align}\qquad\qquad$$

Now find factors $\,d\,$ of $\,ac+b\,$ of form $\,bx+c,\,$ i.e. $\,d\equiv c\pmod{\!b}$.

OP has $\, ac+b = 419\cdot 9319 = $ product of primes, so only a few factors to test.