To find smallest $n$ such that $2^{n} \equiv 111 \pmod{125} $

Question

How to find the smallest natural number $n$ such that $2^{n} \equiv 111 \pmod{125} $.

If we consider $\pmod{5}$ then $2^n \equiv 1 \pmod{5}$. For $n=4k+l$ where $l \in \left\{ 0, 1, 2, 3\right\}$ we get $16^k 2^l \equiv 1 \pmod{5}$ and $2^l \equiv 1 \pmod{5}$, which leads to $l=0$. Therefore, equation reduces to $16^k \equiv 111 \pmod{125}$.

What to do next?

Answer 1

Next solve $16^k\equiv11\pmod{25}$, which yields $k\equiv4\pmod{5}$. Set $k=5m+4$ so that $$16^k\equiv16^4\times(16^5)^m\equiv36\times76^m\pmod{125}.$$ Because $36\times66\equiv1\pmod{125}$ we now want to solve $$76^m\equiv66\times111\equiv76\pmod{125},$$ which shows that $m=1$ will do, corresponding to $n=36$.

Answer 2

By Hensel's lifting lemma we have that $2$ is a generator for $\mathbb{Z}/(5^3\mathbb{Z})^*$, hence this is a job for the discrete logarithm machinery. We may pre-compute $2^{0},2^{11},2^{22},\ldots,2^{121}\pmod{125}$ and $2^{0},2^{1},2^{2},\ldots,2^{10}\pmod{125}$, then perform a simple scan (this is the baby step-giant step approach). Since $$ 2^{33}\cdot 2^{3} \equiv 92\cdot 8 \equiv 111\pmod{125}$$ the answer is given by $33+3=\color{red}{36}$.