# 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.

• Do you mean a palindrome exist for every $prime < 2000$? Otherwise one example is enough to prove this. For example: $1993 \times 1931=3848483$ – pietfermat Mar 24 '18 at 15:59
• Technically, $0\cdot p=0$ is a palindrome for all $p$... – Mastrem Mar 24 '18 at 19:36
• oeis.org/A062888 might be of mild interest. – Barry Cipra Mar 24 '18 at 20:11
• oeis.org/A020485 (and the theorem there under "Comments") might also be of interest. – Barry Cipra Mar 24 '18 at 20:25

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$.

• It should be noted that when removing the $m$ digits, $p$ can't be $2$ or $5$, but they are themselves palindromes – Mastrem Mar 24 '18 at 20:01