# Last digits of a power of 2

Prove that there exists a power of 2 such that the last 1000 digits in its decimal representation are all 1 and 2.

One fact that I think can be used in this problem: if $2^{n}=\cdots dn$ where $d$ is the digit to the left of $n$, then $2^{dn}=\cdots dn$ (A concept that was used in MMO 1978).

Furthermore I have a feeling that reducing $n$ to its binary or ternary base may be of some help.

If one feels that the question is wrong then please mention why this is never possible.

Thanks!

-
Is this from a contest? If so, which one, please. – Gerry Myerson May 30 '13 at 9:12
converting to binary or ternary will be a step backwards, it's a question about it's decimal representation – ratchet freak May 30 '13 at 9:14

Let $n = 1000$. Since $\Bbb Z/10^n \Bbb Z = (\Bbb Z/2^n \Bbb Z)\times(\Bbb Z/5^n \Bbb Z)$, a first step is to inquire about the possible values of powers of $2$ modulo $2^n$ and $5^n$.

The first one is easy : If $k\ge n$, then $2^k \equiv 0 \pmod {2^n}$. And with enough luck, we may find a solution with $k \ge 1000$ so let's not think about $k<1000$ for now.

As for the second one, one can show that the order of $2$ is $4.5^{n-1}$ in the multiplicative group $(\Bbb Z/5^n \Bbb Z)^*$, and so $2$ generates that group :
First, we check that $2$ is of order $4$ modulo $5$, and that $2^4 = 3.5 + 1 \neq 1 \pmod {5^2}$. Since $(2^4)^5 \equiv 3.5^2 + 1 \pmod {5^3} \equiv 1 \pmod {5^2}$, $2$ is of order $20$ modulo $5^2$. And so on, $(2^4)^{5^k} \equiv 3.5^{k+1} + 1 \pmod {5^{k+2}} \equiv 1 \pmod 5^{k+1}$, hence $2$ is of order $4.5^k$ modulo $5^{k+1}$.
This shows that the powers of $2$ modulo $5^n$ are exactly the invertible classes modulo $5^n$, i.e. those not divisible by $5$.

Finally we have to show that there is a class modulo $10^n$ containing only the digits $1$ and $2$ such that it is not divisible by $5$ (easy !), and it is divisible by $2^n$

In fact, we can show that forall $x \in \Bbb Z/2^n \Bbb Z$, there is a unique $y \in \Bbb Z/10^n \Bbb Z$ such that $y$ only uses the digits $1$ and $2$ and $y \equiv x \pmod {2^n}$:
This is true for $n=1$, if $x=1 \pmod {2}$ we pick $y=1 \pmod {10}$ and if $x=0 \pmod {2}$ we pick $y=2 \pmod {10}$. Suppose $n>1$ and let $x' \in \Bbb Z/2^{n-1}\Bbb Z$. Using the induction hypothesis we have a unique $y' \in \Bbb Z/10^{n-1}\Bbb Z$ such that $y' \equiv x' \pmod {2^{n-1}}$. Above $y'$ there are two allowed classes mod $10^n$, $1y$ and $2y$. Since their difference is $10^{n-1} \equiv 2^{n-1} \pmod 2^n$, they are distinct and they give modulo $2^n$ the two classes above $x'$

Applying this proof we get a number $...1212122112$ with $1000$ digits which is divisible by $2^{1000}$ modulo $10^{1000}$, not divisible by $5$, and hence is a power of $2$ modulo $10^{1000}$.

-