40
$\begingroup$

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

$\endgroup$
  • 31
    $\begingroup$ It works for any number, not just primes, and the result divisible by $11$. $\endgroup$ – coffeemath Jan 6 '15 at 21:13
  • 15
    $\begingroup$ @Seth It's still divisible by $11$, though. It just happens to be 11. $\endgroup$ – Ian Jan 6 '15 at 21:18
  • 5
    $\begingroup$ 131 is a palindrome too, but it's not divisible by 11. The argument for divisibility by 11 only works if the number of digits is even. $\endgroup$ – Harald Hanche-Olsen Jan 6 '15 at 21:32
  • 12
    $\begingroup$ @HaraldHanche-Olsen: Any number appended in reverse to itself will necessarily have an even number of digits. $\endgroup$ – Foo Barrigno Jan 6 '15 at 23:38
  • 5
    $\begingroup$ @FooBarrigno Yes, of course. But someone might well assume the result holds for arbitrary palindromes, and I wanted to nip this generalization in the bud. $\endgroup$ – Harald Hanche-Olsen Jan 7 '15 at 18:11
52
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Beautifully explained. $\endgroup$ – John Jan 7 '15 at 19:44
  • $\begingroup$ Thanks, @John. Ps. Enjoy your new gold badge! :) $\endgroup$ – Ilmari Karonen Jan 8 '15 at 10:34
  • $\begingroup$ Sometimes the procedure gives a semiprime of the form $11$ times a prime (which is the closest to a prime we can hope for). This happens for 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$ – Jeppe Stig Nielsen May 18 '18 at 13:21
55
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ @Taylor Alternatively because $10^{2n}+1=(10+1)\cdot(10^{2n-1}-10^{2n-2}+\dots (-1)^{r-1}10^{2n-r} \dots +1)$ which shows where the rule comes from. $\endgroup$ – Mark Bennet Jan 6 '15 at 21:19
  • 1
    $\begingroup$ @zarathustra It is fine! Thank you very much for your answer, also. In fact, I think it is great that you have given an alternate answer to the question! $\endgroup$ – Taylor Jan 6 '15 at 21:22
  • 1
    $\begingroup$ @Taylor, you are very welcome. Glad this could help! $\endgroup$ – zarathustra Jan 6 '15 at 21:23
  • 1
    $\begingroup$ The same link had "If the number of digits is even, add the first and subtract the last digit from the rest." This makes it super easy, since the first and last digits will be the same, and you could do this operation until you exhausted all digits. $\endgroup$ – mbomb007 Jan 7 '15 at 15:06
  • 2
    $\begingroup$ BTW you can use a similar trick to extract perfect three-digit cube roots in your head. $\endgroup$ – imallett Jan 7 '15 at 18:47
27
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ And I will gladly push you over the 10k mark for this answer. :) $\endgroup$ – John Jan 6 '15 at 21:23
  • 1
    $\begingroup$ This is clearer if one exploits the polynomial form of radix notation - see my answer. $\endgroup$ – Bill Dubuque Jan 6 '15 at 22:25
12
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your answer is a bit more rigorous than mine. $\endgroup$ – John Jan 6 '15 at 21:24
  • $\begingroup$ This is the answer I would have given $\endgroup$ – Lubin Jan 7 '15 at 5:11
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.