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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.