pidgeonhole problem need assistance

Question

Suppose you have a sequence 2014, 20142014, 201420142014, . . . Show that there is an element in this sequence such that it is divisible by 2013.

This is a problem I had on an exam and I know that this must be pidgeonhole problem but I was wondering if someone could help me figure out how to get a solution.

All I could figure out was that if you divide 2013 to the first couple you will always have a remainder of 1. Also, your numbers will be 1, 10001, 100010001, etc I was thinking that you have 2013 pidgeonholes and you keep on dividing into the sequence until you reach 2013 remainders, but I feel like I'm not approaching this problem in the right way? Could anyone assist me in figuring this out? Although the exam is over I would like to further my studies and understand problems such as these.

Answer 1

There must exists two of those things that are congruent to each other $\bmod 2013$ since there are finite congruences $\bmod 2013$ but an infinite amount of those things, substract them to get something of the form $20142014\dots201400\dots0$ that is a multiple of $2013$, divide by ten as many times as necessary to get a number of the form $20142014\dots2014$ that is still a multiple of $2013$.

Answer 2

It is possible solving it without the pingehole principle:

By Euler's theorem, $$10000^{\varphi(2013)}-1\equiv 0\pmod{2013}$$

Then, $10000$ is a root of the polynomial $$X^{\varphi(2013)-1}+X^{\varphi(2013)-2}+\cdots+1$$ in $\Bbb Z_{2013}[X]$.

Answer 3

Note that no number in the sequence can be congruent to $0\pmod{2013}$ because repeated multiplication of $3$ gives the periodic sequence $3,9,7,1$ as last digit. So since there are an infinite number of integers and the number of distinct remainder is $2013$, it will suffice to consider first $2014$ numbers of the sequence. By PHP some two of them will give same remainder. Hence done.