2003 USAMO Problems/Problem 1
Revision as of 05:56, 22 April 2007 by Boy Soprano II (talk | contribs)
Problem
(Titu Andreescu) Prove that for every positive integer there exists an -digit number divisible by all of whose digits are odd.
Solution
We proceed by induction. For our base case, , we have the number 5. Now, suppose that there exists some number with digits, all of which are odd. It is then sufficient to prove that there exists an odd digit such that is divisible by . This is equivalent to proving that there exists an odd digit such that is divisible by 5, which is true when . Since there is an odd digit in each of the residue classes mod 5, exists and the induction is complete.