Prove that every positive integer divides a number such as $70, 700, 7770, 77000$.
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.
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*}
Take some integer $n$. Consider the numbers $$x_i= \underbrace{77...77}_i \text{ mod } n\qquad\text{for $i\in\Bbb N$}$$
The pidgeonhole principle tells you that there are $x_i=x_j$ with $i> j$. Then we have $(x_i-x_j)\equiv 0 \pmod n$ (i.e. $n$ divides $x_i-x_j$), as well as
$$x_i-x_j = \underbrace{77...77}_{i-j}\overbrace{00...00}^{j}.$$