<s>[INST] Solve $2^x\equiv 5\pmod{13}$ I know the solution is $x\equiv  9 \pmod{12}$.
I worked it by doing the donkey work of taking powers of $2$ : $2^2, 2^2, 2^3, \ldots, 2^{12}$ and picking the one that reduces to $5$. Just wondering if there is any other efficient method to solve the congruence when the variable is in exponent ? Thanks!
 [/INST] $$2^x\equiv5\equiv-8\equiv-2^3\pmod{13}$$
$$\iff2^{x-3}\equiv-1$$
Now $2^{12}\equiv1\pmod{13}\iff13|(2^6+1)(2^6-1)$ and we actually have $2^6\equiv-1\pmod{13}$
Clearly,$6$ is the smallest positive exponent
$\implies x-3\equiv6\pmod{12}$
</s>