2

I want to show that for each natural number $k$ there is a $k$-digit number divisible by $2^k$ consisting only of the digits $1$ or $2$.

I tried to solve it using induction as follows. For $k=1$, $2^1|a_0=2$. Now suppose for the natural $k$ we have $2^k| a_{k-1}…a_0$ where each $a_i$ is either $1$ or $2$. I don’t know how to insert an appropriate digit to $a_{k-1}…a_0$ so that it will be divisible by $2^{k+1}$, because the new digit as a function of $k$ seems not to obey any obvious pattern. How would we proceed?

  • 1
    Hint. proceed indeed by induction, so you have $2^{k} \mid a_{k-1} \dots a_{0}$, so $a_{k-1} \dots a_{0} = 2^{k} \cdot t$. Now consider the two numbers $1 a_{k-1} \dots a_{0} = 10^{k} + a_{k-1} \dots a_{0}$ and $2 a_{k-1} \dots a_{0} = 2 \cdot 10^{k} + a_{k-1} \dots a_{0}$. – Andreas Caranti Feb 22 '22 at 14:32
  • Have you considered the residue classes that all the possible candidates are mod $2^k$? – JMP Feb 22 '22 at 14:33
  • You have almost solved it. One of the two numbers must be divisible by $2^{k+1}$, which one it is , is not relevant. – Peter Feb 22 '22 at 14:37
  • @JMP This problem doesn’t assume knowledge of residue classes –  Feb 22 '22 at 14:39
  • @AndreasCaranti yes I got it now, thanks –  Feb 22 '22 at 14:52

1 Answers1

1

As one of the comments has suggested, you can simply prove that all such $k$-digit numbers must be distinct $\text{mod}(2^k)$.

This is trivial for $k=1$. We assume that it has been proven for $k=n-1$ and work out the inductive step:

Suppose $\overline {a_n a_{n-1}\ldots a_1}$ and $\overline {b_n b_{n-1}\ldots b_1}$ are congruent $\text{mod}( 2^n)$, where all $a_i$ and $b_j$ are from $\{1,2\}$.

Now, $a_1=b_1$, otherwise they wouldn't even be congruent $\text{mod}(2)$.

It follows that $\overline {a_n a_{n-1}\ldots a_2 \;0} \equiv \overline {b_n b_{n-1}\ldots b_2\;0} \;\;\text{mod}(2^n)$

You now have: $10\times \overline {a_n a_{n-1}\ldots a_2} \equiv 10\times \overline{b_n b_{n-1}\ldots b_2} \; \; \text{mod}(2^n)$.

This is the same as $ \overline {a_n a_{n-1}\ldots a_2} \equiv \overline{b_n b_{n-1}\ldots b_2} \; \; \text{mod}(2^{n-1})$, which means by the inductive hypothesis that they are the same number.

Chris Sanders
  • 7,137
  • 10
  • 23
  • Your answer is about uniqueness, rather than existence as asked in my problem. But it was useful to know the uniqueness too, thanks –  Feb 22 '22 at 15:53
  • Actually, there are $2^k$ such $k$-digit numbers, so if they are all distinct mod $2^k$, this implies one of them must be $0$ mod $2^k$. – Chris Sanders Feb 22 '22 at 15:54
  • Yes exactly, I failed to take it into consideration. Thanks for your clarification –  Feb 22 '22 at 15:56