1
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.