Solving for solutions to a congruence

Question

I am interested in solutions to this congruence:

$$2^kx \equiv x \bmod m$$

Where $m$ and $x$ are known positive integers. They may not necessarily be prime or coprime. I am looking for solutions for $k$. How can I do this?

Answer 1

Let $\,\ d = (M,X),\,\ m = M/d,\,\ x = X/d.\ $ Then

$\quad M\mid X(2^k\!-1)\!\!\overset{\ \div\,d}\iff m\mid x(2^k\!-1)\overset{(m,x)\,=\,1}\iff m\mid 2^k\!-1\iff {\rm ord}_m(2)\mid k$