Post History

Add one to both sides and consider residues modulo $a$ to get $$2^n \equiv 1 \pmod a$$

So you want to find the [multiplicative order of $2$ modulo $a$](https://en.wikipedia.org/wiki/Multiplicative_order). As you note, $2^n \ge a + 1$ so $n \ge \lg(a+1)$; by Lagrange's theorem, $n \le \varphi(a)$, where $\varphi$ is [Euler's totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function). More generally, $n$ is a factor of $\varphi(a)$, so it's easier when you know the factorisation of $\varphi(a)$.