# Prove that for every natural number $n$ there exists some power of 2 whose final $n$ digits are all ones and twos.

Here's the problem :

Prove that for every natural number $$n$$ there exists some power of $$2$$ whose final $$n$$ digits are all ones and twos.

My attempt : Since the final digit of a power of $$2$$ can not be $$1$$ , it has to be $$2$$ , which happens for numbers of the form $$2^{4k+1}$$. For the second last digit , it has to be $$1$$ , as the number would be divisible by $$4$$ (for $$n\ge 2$$). But I couldn't observe any fixed pattern for that .

I am not sure whether this approach is taking me anywhere towards to solution at all .

Could someone please help me solve this problem ?

Thanks!

• This is a straightforward induction and you are very much on the right track. Don’t try to identify any fixed pattern: rather, focus on proving that either $1$ or $2$ works to extend from $k$ digits to $k+1$. You don’t need to know which digit works, just show that if $1$ doesn’t have the right divisibility then $2$ definitely does. – Erick Wong Oct 22 '20 at 5:57

## 1 Answer

Lemma : For any positive integer $$x$$ with $$n$$ digits (leading zeroes allowed), $$x$$ is the last $$n$$ digits of infinitely many powers of $$2$$ if and only if $$2^n \mid x$$ and $$5 \nmid x$$.

Proof of Lemma : The only if condition is trivial. For arbitrarily large powers of $$2$$, we must have $$2^n$$ as a factor, and thus we need $$2^n \mid x$$. Moreover, no power of $$2$$ is divisible by $$5$$, and hence $$5 \nmid x$$. Next, we count the number of $$x$$ that are the last $$n$$ digits of infinitely many powers of $$2$$. We can see that starting from $$2^n$$, all powers of $$2$$ have last $$n$$ digits divisible by $$2^n$$. By the pigeonhole principle, the last $$n$$ digits of powers of $$2$$ starting from $$2^n$$ must be a periodic sequence. Thus, the period must be $$k-n$$, where $$k$$ is the smallest positive integer $$>n$$ such that $$2^k \equiv 2^n \pmod{10^n}$$. This is the same as $$2^{k-n} \equiv 1 \pmod{5^n}$$. By Lifting the Exponent Lemma, the smallest such $$k-n$$ is: $$k-n=4 \cdot 5^{n-1}$$ and thus, this is the period. Thus, there are $$4 \cdot 5^{n-1}$$ strings of last $$n$$ digits that occur infinitely often as last $$n$$ digits of powers of $$2$$.

To prove the if condition, it suffices to show that the number of $$x$$ such that $$2^n \mid x$$ and $$5 \nmid x$$ is also $$4 \cdot 5^{n-1}$$. Since $$2^n \mid x$$, we must have $$x=2^nq$$ for $$q <5^n$$. Since $$q$$ is any non-negative integer coprime to $$5$$, we have $$4 \cdot 5^{n-1}$$ choices, as required.

Now, it suffices to show that we can use $$1$$s and $$2$$s as the last $$n$$ digits to form a number divisible by $$2^n$$ but not by $$5$$. The last part is obvious since the last digit is only $$1$$ or $$2$$. For the first part, we use induction. The base case is trivial. Now, if you can fill last $$n$$ digits to be divisible by $$2^{n}$$, let us say the digits are $$x$$, we can either have $$10^n+x$$ or $$2 \cdot 10^n + x$$ as the last $$n+1$$ digits. We can see that both these numbers are incongruent modulo $$2^{n+1}$$ but are divisible modulo $$2^n$$. Hence, one of them must be divisible by $$2^{n+1}$$, as required.