Last $m$ digits of $2^n$

 Suppose the last $m$ digits of $2^n$ is the number $d(m,n)$. For eg, the last 4 digits of $2^{24} = 16777216$ are $7216$ and so $d(4,24)$ will be the number $7216$. Another example is $d(3,10) = 24$ (or $024$ if we want to write exactly $3$ digits)

Now given a number $X$ of $m$ digits (we pad with leading zeroes to get exactly $m$ digits if needed, like $024$), for $X$ to be the last $m$ digits of some power of $2$ we must have that, there is some $n$ such that

$$ (2^n - X) = 10^m \times Y$$ 

from this it follows that $X$ must be divisible by $2^m$ and that $X$ must be relatively prime to $5$.

This we can state this as follows:

$\textbf{Necessary Conditions:}$ For a number $X$ of $m$ digits (padded with leading zeroes if needed) to be the last $m$ digits of some power of $2$, we require

$$\begin{aligned}& i) X \text{ must be divisible by } 2^m\\ & ii) \gcd(X,5) = 1\end{aligned}$$

The puzzle is to prove that, the above necessary conditions are also sufficient! i.e 

$\textbf{Prove that:}$

$\textbf{Claim:}$ If $X < 10^m$ is divisible by $2^m$ and $\gcd(X,5) = 1$, then there exists some $n$ such that last $m$ digits of $2^n$ are $X$ (padded with leading zeroes if required). i.e. There is some $n$ such that $d(m,n) = X$.

For eg $X = 24$ is divisible by $8 = 2^3$ and $\gcd(24,5) = 1$. There must be a power of $2$ that ends with $024$ ($2^{10} = 1024$  for eg). Another example, $X = 408$ is divisible by $8$ and $\gcd(408,5) = 1$. The smallest power of $2$ that ends with $408$ is $2^{83}$.

Scroll down for a proof.

.

.

.

.

.

$\textbf{Proof:}$

We need $2^n - X = 10^m Y$ for some $n$. Let $X = 2^m Q$, then we need to have that

$$2^{n-m} = Q \mod 5^m$$

and $\gcd(Q,5) = 1$.

Now $2^{10} = -1 \mod 25$ and the smallest power of $2$ which is $1 \mod 25$ is $2^{20}$. 

Thus $2$ is a primitive root of $25$. Now by a standard theorem of number theory (a primitive root of $p^2$ is also a primitive of $p^t$), this implies that $2$ is a primitive root of $5^t$ for any $t$, and in particular, $t = m$.

Since $\gcd(Q,5) = 1$, there is some $r$ such that $$2^r = Q \mod 5^m$$

And we are done, as we can choose $n = r + m$. 

In fact given $0 < Q < 5^m $ such that $\gcd(Q,5) = 1$, there is a unique $r_Q$ such that $0 \le r_Q < 4 \times5^{m-1}$ and for any $n = r_Q + m \mod (4 \times 5^{m-1})$ we have $d(m,n) = 2^m Q$.