Solution to the modulo 5^n riddle
Introduction
Orna Agmon Ben-Yehuda asked this riddle on her blog back in 1 December, 2009. Here is my solution to it.
Solution:
The Problem
We need to prove that for every natural number $n > 0$, there exists a decimal number of $n$ digits, which can be wholly divided by $5^n$, and all of its digits are odd.
Methodology
We will prove a stronger claim. We will demonstrate that if $b_n$ is the corresponding number for $n$, then it can serve as a suffix for $b_{n+1}$, by adding another most significant digit.
More formally:
$b_1$ = 5.
For every $n$, there exists an $a \in \{1,3,5,7,9\}$ so that $b_{n+1} = b_n + a \cdot 10^n$ and $b_{n+1} \mod 5^{n+1} = 0 $.
Proof
The proof would be by induction.
Induction Base
It holds for $n = 1$ as 5 is a one-digit number that is wholly divisible by $5^1$.
Induction Step
Let's assume it holds for $n$ and show that it also holds for $n+1$.
Now:
\[b_{n+1} = b_n + a \cdot 10^n \]
According to the induction step $b_n$ is wholly divisible by $5^n$ and so is $10^n = 5^n \cdot 2^n$. So we can divide the expression by $5^n$ and try to find an $a$ so that the quotient is divisible by 5. We get:
\[ b_{n}' + a \cdot 2^n \]
$b_{n}'$ has some modulo 5, and $2^n$ has a non-zero modulo. The values that $a$ can assume (1,3,5,7,9) contain all the moduli of 5. Since 5 is prime, and its moduli are a group, we can get all moduli by multiplying a given non-zero modulo by the other moduli. So we can choose an $a$ so that the expression modulo 5 evaluates to 0. Thus we can divide this $b_{n+1}$ by $5^{n+1}$ as well.
Q.E.D.