TITLE: Number divisible by 7 inside a seven digit number
QUESTION [4 upvotes]: Let $x$ a seven-digit number. Prove that only by erasing numbers from the left side or the right side (or both) of the number, you can remain with a number that is divisible by $7$.
You probably need the Pigeonhole Principal here, but I didn't know how to use it. That's why I'd like to get a hint (or the full proof with a hint beforehand). Thanks

REPLY [6 votes]: Let our number be $n=\overline {a_7a_6a_5a_4a_3a_2a_1}$
Now consider the $7$ numbers $n_i=\overline {a_i\cdots a_1}\pmod 7$.
As there are $7$ of these we either hit every reside class $\mod 7$ or we hit one twice.  If we hit all the classes we must hit $0$.  If we hit some class twice, say $n_i\equiv n_j\pmod7$ for some $i<j$ then it is easy to see that $\overline {a_j\cdots a_{i+1}}\equiv 0 \pmod 7$ and we are done.
Example:  take $n=1248123$.  Then, $\pmod 7$ we get $$\{n_1,\cdots, n_7\}\equiv \{3,2,4,3,5,1,2\}\pmod 7$$
We see that $n_1\equiv n_4\pmod 7$ so $$8123\equiv 3\pmod 7\implies 7\,|\,8120\implies 7\,|\,812$$
Or $$n_7\equiv n_2\pmod 7\implies 7\,|\,12481$$
Here, of course, we are relying on the fact that $\gcd(7,10)=1$.  The claim generalizes from $7$ to any $m$ prime to $10$ using the same argument.
{"set_name": "stack_exchange", "score": 4, "question_id": 3871287}