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

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?

• Sage says $n=36$ – Oldboy Nov 19 '18 at 9:02
• I think $2^n\equiv 111\equiv -14\pmod{125}$ implies that $2^n\equiv 11\pmod{25}$ – 1ENİGMA1 Nov 19 '18 at 10:37
• Maybe, similar implicity used here:math.stackexchange.com/questions/1133616/… – 1ENİGMA1 Nov 19 '18 at 10:39
• @1ENİGMA1 That questions solves $n^3\equiv888\pmod{1000}$, which is quite a different question. – Servaes Nov 19 '18 at 11:30
• @Servaes, I shared it because of answers ajotatxe. – 1ENİGMA1 Nov 20 '18 at 5:57

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