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.


  • 1
    $\begingroup$ Is this from a contest? If so, which one, please. $\endgroup$ – Gerry Myerson May 30 '13 at 9:12
  • 1
    $\begingroup$ converting to binary or ternary will be a step backwards, it's a question about it's decimal representation $\endgroup$ – 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}$.


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.