Palindrome multiple of prime Let $p$ be a prime number less than $2000$. Prove that there exists a multiple of $p$ that is a palindrome and has at most $450$ digits.
We can assume that $p>9$ (in the case $p\leq 9$, $p$ is a palindrome itself). One possibility is to look at the numbers $1,10,100,1000,\dots$. If we consider the first $2000$ numbers, some two must have the same remainder when divided by $p$, so this gives $p\mid 10^x-10^y$, and since $\gcd(p,10)=1$, we get $p\mid 10^{x-y}-1$ which is a palindrome. But it can have up to $2000$ digits.
 A: Define the sequence $(a_k)_{k=1}^{2007}$ by:
$$a_{9k+l}=9\left(\sum_{i=0}^{k-1}(10^{449-i}+10^i)\right)+l(10^{449-k}+10^k)$$
for $0\le k\le 222$ and $1\le k\le 9$
The sequence starts like:
\begin{align*}
a_1 &= 100\dots001\\
a_2&=200\dots002\\
&\vdots\\
a_9&=900\ldots009\\
a_{10}&=910\dots019\\
a_{11}&=920\dots029\\
&\vdots\\
a_{18}&=990\dots099\\
a_{19}&=991\dots199\\
&\vdots
\end{align*}

Since $p<2000$, there are at least two $i\neq j$ with $a_i\equiv a_j\pmod p$, by the pigeonhole principle.
Suppose the first $m$ digits of $a_i$ and $a_j$ are identical, then the last $m$ are as well, since they are symmetric in base $10$. Remove the first and last $m$ digits from $a_i$ and $a_j$ and call the new integers $b$ and $c$. It is clear that $b\neq c$ and $b\equiv c\pmod p$
Suppose WLOG that $b>c$. The sequence has been designed in such a way, that when subtracting $c$ from $b$, there will be no carry-operations. 
Now, $b-c$ is the difference between two palindromes with the same number of digits with different first digits and when taking the difference, there will be no carry operations. This means that $b-c$ is a palindrome of at most $450$ digits, which is divisible by $p$.
