Prove that every positive integer divides a number such as $70, 700, 7770, 77000$, whose decimal representation consists of one or more $7$’s followed by one or more $0$’s.
Hint:$7$; $77$; $777$; $7777$
I know that I am supposed to use the pigeonhole principle, but I can't figure out how. I know that it probably comes down to proving that all odd numbers divide some number of the form $7, 77, 777$, etc.
Best Answer
Consider the set of numbers $7 \times \sum_{i=0}^{M} 10^i$ for $M=0, \cdots N$ (That is the set of numbers, of length $1$ to $N+1$, all of whose digits are $7$). There are $N+1$ elements. Now consider them modulo $N$ . By the pigeon hole principle, there must be two that are congruent, subtract these and they will be divisible by $N$.
Edit: Let $a_{M} = 7 \times \sum_{i=0}^{M} 10^i$ (The $M+1$ digit number consisiting of only $7$'s) and $a_{M} \equiv b_{M} \pmod {N}$. There are only $N$ possible values for the $b$'s, so by the PHP there exist two $M$ values that are equal, say $p$ and $q$ (with $p>q$). We have $ a_{p} \equiv a_q \pmod {N}$. "Subtract these" and we have
\begin{eqnarray*} a_{p} - a_q = \underbrace{7 \cdots 7 }_{p-q \text{ 7's}} \underbrace{0 \cdots 0 }_{q+1 \text{ 0's}} \equiv 0 \pmod {N}. \end{eqnarray*}