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$.
...
I've tried solving the same problem yesterday. I managed to brute-force my way to finding all fair and square (palindromes whose square root is a palindrome) numbers from 1 to $10^{14}$:
1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001,
1234321, 4008004, 100020001, 102030201, 104060401, 121242121,
123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201,
12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001,
1004006004001, 1020304030201, 1022325232201, 1024348434201,
1210024200121, 1212225222121, 1214428244121, 1232346432321,
1234567654321, 4000008000004, 4004009004004
My solution was correct, and the second dataset was solved. But I couldn't find a proper way to calculate all fair and square numbers up to $10^{100}$.
I showed this to my wife this morning, and she noticed an interesting pattern of numbers within my list:
121, 10201, 1002001, 102030201, 10000200001, 1000002000001
484, 40804, 4008004, 400080004, 40000800004, 4000008000004
12321, 1002003002001,
Some fair and square numbers re-appear with space padding. Let's try beyond $10^{14}$. Adding some zeros to $1020302030406040302030201$, whose square root is $1010100010101$ - a palindrome!
Wish I had my wife with me when I solved this yesterday.
I don't have a mathematical explanation for this phenomena, but I guess that for some reason, every fair and square number beyond a certain boundary can be built by adding zeros to a smaller palindrome.
Best Answer
As a counterexample for odd length, $121$ and $131$ are relatively prime. More generally,
$$1...121...1$$ and $$1...131...1$$ will always be relatively prime, since their difference will be of the form $2^k 3^j$ for some $k$ and $j$.