Prove that for every integer power of 2, there exists a multiple of it with all digits (in decimal expression) not zero.
Problem
Source: China TST 1990, problem 7
Tags: modular arithmetic, induction, number theory unsolved, number theory
27.06.2005 14:55
More precisely, it is well-known (and probably already solved here) that fro each positive integer $n$, there exist a integer whose decimal expansion only uses digits $1$ or $2$ and which is divisible by $2^n.$ Pierre.
25.06.2014 10:34
Ya...we look for a number of the form $1111\cdots12$ with $k+1$ digits.This number is precisely of form $10^k+10^{k-1}+\cdots+10+2=2(5\times \frac{10^k-1}{9}+1)$ so we have to choose a $k$ such that $5(10^k-1)+9 \equiv 0\pmod{2^n}$.But clearly there exists such $k$.(Basically we are solving the system of congruences modulo $2^n$ which is 9=-1 modulo 5.There are infinetely many such triples.Then we solve the congruence $10^k-1 \equiv t\pmod{2^n}$ where $t$ is one such solution).
25.06.2014 11:12
sayantanchakraborty wrote: But clearly there exists such $k$.(Basically we are solving the system of congruences modulo $2^n$ which is 9=-1 modulo 5.There are infinetely many such triples.Then we solve the congruence $10^k-1 \equiv t\pmod{2^n}$ where $t$ is one such solution). BUT This is ABSOLUTELY FALSE!!! how about $k$ if $n=4, 5, 6$
02.07.2014 12:02
pbornszstein gave a correct hint, I will only elaborate it. The hint is well-known too, so don't make a mistake that any of this is mine, the idea is taken from some book(s). Anyways induction works. We need something more. We claim we can find a $n$-digit solution actually. Suppose we have a $n$-digit integer consisting of only $1,2$ that is divisible by $2^n$. Let it be $a_n$. Now suppose $2^{n+1}\mid a_n$. Then we will append a $2$ before $a_n$ and define it to be $a_{n+1}$ , and if that is not the case then we append a $1$, and call it $a_{n+1}$. To understand this : $a_1=2\mapsto a_2=12\mapsto a_3=112\mapsto a_4=2112\mapsto a_5=22112\mapsto \cdots$ I hope the idea is clear now. So the induction finishes the proof.