Divisibility Tests for Palindromes?

Let $n$ be a positive integer. My question, loosely, is

• Which palindromes are divisible by $n$?

Of course, the question has the easy answer "those that are divisible by $n$" unless I specify in what terms I want to characterize the divisibility. I'm not quite sure myself of how to answer this, so I will give some examples and general thoughts here, which will hopefully convey the spirit of the question.

Example of what I'm looking for:

• Every palindrome with an even amount of digits is divisible by $11$

Example of what I'm not looking for:

• A non-zero palindrome is divisible by $5$ if and only if it starts with a $5$

Both of these examples are found by applying some well known divisibility rules. The example of what I'm looking for is the case of the divisibility rule for $11$, which lets on simply check the alternating sum of the digits. But the nice thing is that one doesn't need to know any specific digits of the palindrome; only its length and the fact that it is a palindrome are needed. It is also a little less obvious than the example of what of I'm not looking for (at least to me.) Are there any other of these "cute" rules which let one easily see that a palindrome is or is not divisible by a certain integer? Has anyone ever studied this question in more detail?

I understand that the question of checking whether a certain number is divisible by another is already hard by itself, so maybe the question should be rephrased as

• For which integers $n$ and $P$ we can use the fact that $P$ is palindromic to our advantage in determining whether $n$ divides $P$?

Finally, as a sort of bonus question if anything in this direction is possible, I am particularly interested in the case in which $n$ is itself palindromic, i.e. determining whether a palindrome possesses a palindromic factor.

Thanks in advance for any thoughts whatsoever on the issue.

• Project Euler? – Billy Rubina Sep 13 '12 at 9:53
• @GustavoBandeira No, just random curiosity. Which Project Euler challenge are you referring to? – user38355 Sep 14 '12 at 21:47

An interesting case is $n=101$.

The $3$-digit palindrome $aba$ is divisible by 101 iff $b=0$.

The $4$-digit palindrome $abba$ is divisible by 101 iff $a=b$.

The $5$-digit palindrome $abcba$ is divisible by 101 iff $c=2a$.

The $6$-digit palindrome $abccba$ is divisible by 101 iff $a+b=c$.

The $7$-digit palindrome $abcdcba$ is divisible by 101 iff $d=2b$.

The $8$-digit palindrome $abcddcba$ is divisible by 101 iff $a+d=b+c$.

The $9$-digit palindrome $abcdedcba$ is divisible by 101 iff $e = 2(c-a)$.

The $10$-digit palindrome $abcdeedcba$ is divisible by 101 iff $a+b+e=c+d$.

...

Consider the palindrome abcddcba. This is $$10000001a+(10)(100001)b+(100)(1001)c+(1000)(11)d$$ The only thing the numbers 10000001, 1000010, 100100, and 11000 have in common (as far as anything useful for divisibility goes) is that they are all divisible by 11, so it's unlikely that knowing $P$ is a palindrome is going to tell you anything useful about divisibility by $n$, except for $n=11$.

Now $10^2+1,10^6+1,10^{10}+1,\dots$ are all divisible by $101$, so if you ever get a number c0b0a0a0b0c or d0c0b0a0a0b0c0d, and so on, you'll know it's a multiple of 101. Similarly, c00b00a00a00b00c and the like will be divisible by 1001, and so on.

In any odd base, a palindrome of even length is divisible by $2$. In any base $b\equiv1\bmod n$ with $n$ odd, a palindrome of even length is divisible by $n$ iff its halves are. In particular, in base $10$ a palindrome of even length is divisible by $3$ or $9$ iff its halves are.