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!
Best 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.