2003 USAMO Problems/Problem 1

Problem

(Titu Andreescu) Prove that for every positive integer $\displaystyle n$ there exists an $\displaystyle n$ -digit number divisible by $\displaystyle 5^n$ all of whose digits are odd.

Solution

We proceed by induction. For our base case, $\displaystyle n=1$ , we have the number 5. Now, suppose that there exists some number $\displaystyle a \cdot 5^{n-1}$ with $\displaystyle n-1$ digits, all of which are odd. It is then sufficient to prove that there exists an odd digit $\displaystyle k$ such that $k\cdot 10^{n-1} + a \cdot 5^{n-1} = 5^{n-1}(k \cdot 2^{n-1} + a)$ is divisible by $\displaystyle 5^n$ . This is equivalent to proving that there exists an odd digit $\displaystyle k$ such that $k \cdot 2^{n-1} + a$ is divisible by 5, which is true when $k \equiv -3^{n-1}a \pmod{5}$ . Since there is an odd digit in each of the residue classes mod 5, $\displaystyle k$ exists and the induction is complete.