Prove that for every positive integer $n$ there exists an $n$-digit number divisible by $5^n$ all of whose digits are odd.
Problem
Source:
Tags: induction, modular arithmetic
22.09.2007 03:04
We will prove the result using mathematical induction. Base Step For $ n = 1$ we can take the $ 1$-digit number $ 5$ and $ 5$ is odd, which is divisble by $ 5^{1}$, so the result is true for $ n = 1$ Induction Step Assume the result is true for $ n = k$ and let $ q$ be the $ k$-digit number composed only of odd digits and divisible by $ 5^{k}$. Then, $ q = 5^{k}*t$ where $ t$ is a positive integer. Of the numbers $ 1*2^{k}+t, 3*2^{k}+t, 5*2^{k}+t, 7*2^{k}+t, 9*2^{k}+t$ each gives a different residue $ \pmod 5$, because if we assume two numbers $ a*2^{k}+t, b*2^{k}+t$ have the same residue $ \pmod 5$ where $ a,b\in\{1,3,5,7,9\}$ and $ a$ and $ b$ are not equal, then $ a*2^{k}+t-( b*2^{k}+t)\equiv 0\pmod 5$ so $ (a-b)2^{k}\equiv 0\pmod 5$, but $ 2^{k}$ and $ 5$ are coprime as $ 2,5$ are coprime; also $ (a-b)\in\{-8,-6,-4,-2,2,4,6,8\}$ so $ 5$ and $ a-b$ are coprime. Hence, we cannot have $ a*2^{k}+t-( b*2^{k}+t)\equiv 0\pmod 5$ so of the numbers $ 1*2^{k}+t, 3*2^{k}+t, 5*2^{k}+t, 7*2^{k}+t, 9*2^{k}+t$ each gives a different residue $ \pmod 5$. But then, because there are $ 5$ different residues $ \pmod 5$ then one of the numbers $ 1*2^{k}+t, 3*2^{k}+t, 5*2^{k}+t, 7*2^{k}+t, 9*2^{k}+t$ gives a residue of $ 0\pmod 5$, let this number be $ x*2^{k}+t$, where $ x\in\{1,3,5,7,9\}$, then the number $ (x*2^{k}+t)5^{k}$ is divisible by $ 5^{k+1}$. But $ (x*2^{k}+t)5^{k}= x*10^{k}+5^{k}*t = x*10^{k}+q$, which is the number with the first digit $ x$ followed by the decimal representation of $ q$, so we get a $ k+1$-digit number $ r$ composed only of odd digits (as $ x$ is odd and all digits of $ q$ are odd) and divisible by $ 5^{k+1}$, so the result is true for $ k+1$, Hence the result of the problem follows by mathematical induction.