# Can $a \equiv x \cdot b$ (mod $m$) be solved for $x$?

Suppose I have $a \equiv x \cdot b$ (mod $m$) and I know the value of $a, b, m$.
The value of $m$ is of the form $2^n$ (I don't know if that even helps)...

I want to know if there exist a unique value of $x$ in $[0, m -1)$ that satisfies the equation. And if so, then how do I obtain it?

This is what I've done so far:

First I considered $a$ and $b$ to be between $0$ and $m-1$

$a \equiv x \cdot b$ (mod $m$)
$$m | (bx - a)$$ $$bx - a = km$$ $$x = \frac{km + a}{b}$$ Since $x$ ranges from $0$ to $m-1$, $k$ must be from $0$ to $b-1$

I'm confused how to proceed from here...

• Do you know the extended Euclidean algorithm and the Bézout indetity? – quid Aug 30 '16 at 14:18

This equation has a unique solution if and only if $b$ is a unit modulo $m$, which happens if and only if $b$ and $m$ are coprime.
To solve $$a\equiv xb\pmod{m}\tag{1}$$ we can solve $$xb+ym=a\tag{2}$$ which requires $\gcd(b,m)\mid a$. Thus, we would like to solve $$x\frac{b}{\gcd(b,m)}+y\frac{m}{\gcd(b,m)}=\frac{a}{\gcd(b,m)}\tag{3}$$ To solve $(3)$, we can use the Extended Euclidean Algorithm. One implementation is detailed in this answer.