Palindrome is a sequence of digits which doesn't change if we reverse the order of its digits. Prove that a sequence $(x_n)^{\infty}_{n=0}$ defined as $x_n=2013+317n$ contains infinitely many numbers with their decimal expansions being palindromes.
Problem
Source: 2nd European Mathematical Cup
Tags: induction, number theory open, number theory
16.12.2013 22:13
Well, we have $2013\equiv 111[317]$, so it's clearly enough to show that there is infinitely many palindromes in $111+317n$. Because $317\cdot 347=109999$, we get, that $10999900+111=11000011$ is in the sequence, then also $1099990000000+11000011=1100001000011$ is in the sequence and so on. We get by induction that $1100001000010000100\dots 00100001000011$ is in the sequence, so there is clearly infinitely many palindromes. Q.E.D.
17.12.2013 00:01
Or simply prove that the congruence 10^m + 1 - 2013 = 0 (mod 317) has infinitely many solutions in N. But unfortunately I didn't have the opportunity to seriously look all the problems.
17.12.2013 16:15
Please check my solution: we have $2013 = 111 (mod 317)$ We assume that there exist infinitely many palindromes, that satisfy the given condition, of the form $1111..111111$. So the number $111...11111$ must give the remainder $111$, or in other words $11111...111-111$ must be divisibly by $317$ for infinitely many numbers. As $1000$ is not divisible by $317$, there must exist infinitely many numbers $111....1111$ divisible by $317$. But it is well-known lema - since $317$ is a prime number, there exist infinitely many numbers of the form $111...111$ for each pirme, that they divide this number (we can prove it by Dirichlet's theorem).
17.12.2013 17:53
It's completely ok.