# There exists an integer with alternating digits $1$ and $2$ which is divisible by $2013$

Could someone give me hints in how to solve the following (rather interesting) problem?

Prove that there exists an integer consisting of an alternance of $1$s and $2$s with as many $1$s as $2$s (as in $12$, $1212$, $1212121212$, etc.), and which is divisible by $2013$.

Source: Problem 4 in this document.

Among the first 2014 numbers of this kind, two must have the same remainder mod $2013$.

• Just brilliant. Many thanks :) – Prism Dec 31 '13 at 9:15
• This is formally known as en.wikipedia.org/wiki/Pigeonhole_principle – lab bhattacharjee Dec 31 '13 at 9:18
• Actual solution can be obtained by Fermat's theorem. It is 12 repeated 660 times. I had to answer before 2013 ended :-) – user44197 Dec 31 '13 at 9:36

Hint:

Consider the numbers: the sequence of integers $12,1212,121212,12121212,.......$

Two of them must be equal modulo $2013$.Hence, the difference of these two must be divisible by $2013$. Now use this difference to obtain the desired number (note that $2,5\not|2013$)

• Thanks for more detailed explanation :D – Prism Dec 31 '13 at 9:18

note $3$ has to divide the number. So what can you say about the sum of the digits?

$11 has to divide the number. So what can you say about the sum of digits in the odd location and even location. Once you have fixed these two, you want$61$divide the number. I am glad that 2013 is not a prime number :) In response to the comment by OP: Suppose the number starts as$12$. It is not clear if the length has to be even, but I will assume that. Then every time you add another$12$you are muliplying by 100 and adding 12. So $$P_{n+1} = 100 P_n + 12$$ Solving we have $$P_n = 4 \times \frac{100^n-1}{33}$$ Since$61$divides$P_n$, by Fermat's theorem $$n = 60 k$$ Number is clearly divisible by 3. Working modulo$11$we have $$P_{n+1} = P_n + 1$$ So $$P_1 = 1\\ P_2 = 2 \\ P_3 = 3 \\ P_4 = 4$$ Hence$n$has to be a multiple of 11. The smallest$n$is 660. So the number is$12$repeated 660 times. • How do you make$61$divide the number? I don't immediately see it. At least for divisibility by$3$and$11$, we have the the known criterions… Never heard of one for 61. :) – Prism Dec 31 '13 at 9:19 • Trial and error. But is better than trying out 2014 numbers, the largest having 4028 digits! – user44197 Dec 31 '13 at 9:20 • Haha well, I multiplied$61$by$10k+2$for$k=0, 1, 2, 3, 4, … 15$, but I haven't gotten single number of the form$121212…12$– Prism Dec 31 '13 at 9:27 • It is 12 repeated 660 times. See my update – user44197 Dec 31 '13 at 9:35 • Finding a formula for$P_n\$ is an interesting idea. Thanks for taking your time for updating the answer (+1). This is a very concrete approach to the problem! – Prism Dec 31 '13 at 9:40