If a prime number is reversed, and then appended to itself, why is the result always a composite number?

$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?

Solution 1:

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.$$

Solution 2:

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$.)

Solution 3:

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.

Solution 4:

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 $$

Solution 5:

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$.