4
$\begingroup$

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!

$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$ – Erick Wong Oct 22 '20 at 5:57
1
$\begingroup$

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.

$\endgroup$

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.