Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
$2 \Rightarrow 22$ which is a composite number.
$37 \Rightarrow 3773$ which is a composite number.
$523 \Rightarrow 523325$ which is a composite number.
$8123 \Rightarrow 81233218$ which is a composite number.
If you take any prime, reverse it, and append it to itself, the result always seems to be a composite number. I have checked this for $2 \leq n \leq 999999$.
Is there a reason for this, or is it simply a coincidence?
All numbers of this kind are divisible by $11$.
Consider prime $\mathit{abcdefg}$ where each letter is a digit.
The number $\mathit{gfedcbaabcdefg}$ is divisible by $11$ because the alternating sum of digits is always zero:
$$g - f + e - d + c - b + a - a + b - c + d - e + f - g = 0.$$
As John's answer notes, every palindromic number with an even number of digits is divisible by $11$, because the alternating sum of its digits is zero (and thus a multiple of $11$).
For example, for $81233218$, we have: $$8-1+2-3+3-2+1-8 = 0,$$ and so $81233218$ is divisible by $11$.
The reason why this divisibility rule works is most easily seen using a bit of modular arithmetic.
Specifically, by definition, two numbers $a$ and $b$ are equivalent modulo $m$ (which we write as $a \equiv b \pmod m$) if and only if their difference $a-b$ is divisible by $m$. Thus, in particular, a number $n$ is divisible by $m$ if and only if $n \equiv 0 \pmod m$.
Now, the reason this definition is handy is because we can "do arithmetic under the modulus $m$": in particular, if $a \equiv a' \pmod m$ and $b \equiv b' \pmod m$, then $a+b \equiv a'+b' \pmod m$ and $ab \equiv a'b' \pmod m$. Thus, if we're only interested in the result of a calculation modulo some number $m$ (like, say, if we just want to know whether $n \equiv 0 \pmod{11}$ for some number $n$), and the calculation only involves operations that work equivalently "under the modulus" (such as addition and multiplication, and any combination thereof), then we can freely add or subtract multiples of $m$ from any intermediate values to make them more convenient (which often means "closer to zero").
In particular, from the definition it clearly follows that: $$10 \equiv -1 \pmod{11},$$ since $10 - (-1) = 10 + 1 = 11$. We also know that the numerical value of a base-$10$ number is mathematically obtained by multiplying its lowest digit with $1$, the second digit with $10$, the third digit with $10^2 = 100$, etc., and adding the results together. For example: $$81233218 = 10^7 \cdot 8 + 10^6 \cdot 1 + 10^5 \cdot 2 + 10^4 \cdot 3 + 10^3 \cdot 3 + 10^2 \cdot 2 + 10 \cdot 1 + 8.$$
But since $10 \equiv -1 \pmod{11}$, if we only want to calculate the value of the number modulo $11$, we can replace $10$ with $-1$ in this calculation! Thus: $$81233218 \equiv (-1)^7 \cdot 8 + (-1)^6 \cdot 1 + (-1)^5 \cdot 2 + (-1)^4 \cdot 3 + (-1)^3 \cdot 3 + (-1)^2 \cdot 2 + (-1) \cdot 1 + 8 \pmod{11}.$$
And, of course, we can easily see that the powers of $-1$ simply alternate between $-1$ and $1$, so this expression simplifies down to: $$81233218 \equiv -8 + 1 -2 + 3 - 3 + 2 - 1 + 8 = 0 \pmod{11}.$$
(Ps. The same trick also works in bases other than $10$, showing that any number palindromic in base $b$, with an even number of base-$b$ digits, is necessarily divisible by $b+1 = 11_b$.)
2, 3, 5, 7, 11, 14, 16, 19, 31, 32, 34, 38, 71, 74, 79, 91, 92, 94, 100, .... If you want to start with a prime only, it is 2, 3, 5, 7, 11, 19, 31, 71, 79, .... These sequences do not appear in OEIS.
$\endgroup$
May 18, 2018 at 13:21
As has been pointed out in the comments, this is not a special property of the primes. Rather it's true that whenever you reverse a number and append the result to itself, the result is always divisible by 11.
To see why this is true, consider the number $A = 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^0 a_0$, where $a_0, \ldots, a_{n-1}$ are all integers in $\{ 0, \ldots, 9 \}$ - that is, the ordinary decimal expansion of $A$. Then you can write A followed by its reversal as
$$ 10^n (10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^0 a_0) + (10^{n-1} a_0 + 10^{n-2} a_1 + \cdots + 10^0 a_{n-1})$$
and now let's rearrange this so that the terms with the same $a_i$ are together. It equals
$$ a_{n-1} (10^{2n-1} + 10^0) + a_{n-2} (10^{2n-2} + 10^1) + \cdots + a_0 (10^n + 10^{n-1}). $$
Each factor of the form $10^k + 10^l$, where $k-l$ is odd, is divisible by 11. To see this you can factor
$$10^k + 10^l = 10^l (10^{k-l} + 1) = 10^l (10 + 1) (10^{k-l-1} - 10^{k-l-2} + \cdots + 1), $$ where the signs in the last factor are alternating. This is just the well-known rule for factoring sums of $n$th powers
$$(a+b)^n = (a+b) (a^{n-1} - a^{n-2} b + a^{n-3} b^2 - \cdots - a b^{n-2} + b^{n-1}), $$
which applies when $n$ is odd.
So our number is a sum of integer multiples of 11, and is therefore divisible by 11.
Hint $\ $ If in radix $b,\,$ we have $\,n = f(b) = f_0\! + f_1 b +\,\cdots+ f_n b^n,\,$ then reversing the digits of $\,n\,$ yields the integer $\,\bar n = \bar f(b)\,$ for $\,\bar f(b) = b^n f(b^{-1})$ the reversed polynomial. Appending yields
$$ {\rm mod}\,\ b\!+\!1\!:\,\ b\equiv -1\,\Rightarrow\, b^{n+1} f(b) + b^n f(b^{-1})\,\equiv\, (-1)^n f(-1)(-1 + 1)\,\equiv\, 0\qquad $$
Every number obtained by this construction is divisible by $11$. Here is a simple test for divisibility by $11$: if the number is $a_r\cdots a_0$, it is divisible by $11$ iff $\sum_{i=0}^r (-1)^ia_i = 0$. This follows from the fact that $10^{2i+1}=-1\bmod{11}$ and $10^{2i} = 1\bmod{11}$. Thus, $a_r\cdots a_0 = \sum 10^ia_i = \sum (-1)^i a_i\bmod{11}$.
Now, since every digit of the number you construct appear in an odd and an even place, the whole number is divisible by $11$.
Another way to realize this is to break it down as far as we can, and consider a basic "building block": any number of the form $$1\underset{2n}{\underbrace{0...0}}1 - 11= \underset{2n}{\underbrace{9...9}}0$$ if we divide the number on the right hand side with 11, we get an integer with pattern of $n$ "09"s.
This gives some intuition why any position of digits of a palindromic number should be divisible by 11. What is left is to "move" the pieces into place and multiply them with the corresponding digit. The first one is a multiplication with a $10^k$ which does not destroy divisibility and neither does the second. Also we need that addition of numbers divisible preserve divisibility, and it does!
