1
$\begingroup$

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

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

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.

There is a fast algorithm to find the solution: Euclid's algorithm.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.