# Proof for divisibility rule for palindromic integers

I am studying for a test and came across this in my practice materials. I can prove it simply for some individual cases, but I don't know where to start to prove the full statement. Can you help me?

Prove that every palindromic integer in base $k$ with an even number of digits is divisible by $k+1$

-

Do you know that if $m$ is odd then $x+1$ is a factor of $x^m+1$? Do you see how to use this to answer the question?

-

You could apply the generalized divisibility test for 11: a base $k$ number is divisible by $k+1$ iff the sum of its odd digits minus the sum of its even digits is divisible by $k+1$. (In particular, if a number is palindromic and has an even number of digits, it's easy to see that its odd and even digits sum to the same number.)

-
This just shifts the difficulty onto the proof that this generalized divisibility test works. – Gerry Myerson Aug 15 '11 at 12:42
@Gerry Myerson: Well, yes, but that's a known result. :) (In fact, I just linked to a proof.) – Ilmari Karonen Aug 15 '11 at 13:58

HINT $\rm\ \ mod\ \ x+1:\ \ f(x) + x^{n+1}\:(x^n\ f(1/x))\ \equiv\ f(-1) - f(-1)\:\equiv\: 0$

Remark $\ \$ It is simple to verify that $\rm\ x^n\ f(1/x)\$ is the reversal of a polynomial $\rm\:f\:$ of degree $\rm\:n\:,\:$ therefore the above is the general palindromic polynomial with even number of coefficients.

-

The second claim written below will prove your result. In general, you can mimic the divisibility tests for $9$ and $11$. $9$ and $11$ have simple divisibility rules since we deal with decimal number system i.e. base $10$. You can develop divisibility rules for $k$, on a similar note, by expressing it either in base $k+1$ (or) base $k-1$.

Claim 1:

One possible divisibility for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n+1$'. Let '$s$' denote the sum of digits of '$a$' expressed in base '$n+1$'.

Now $n|a \iff n|s$. More generally, $a \equiv s \pmod{n}$

Example:

Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $14$.

$611 = 3 \times 14^2 + 1 \times 14^1 + 9 \times 14^0 = (319)_{14}$

where $(319)_{14}$ denotes that the decimal number $611$ expressed in base $14$. The sum of the digits $s = 3 + 1 + 9 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.

Proof:

The proof for this claim writes itself out. Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n+1$'.

$a = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0$

Now, note that

$$n+1 \equiv 1 \pmod n$$ $$(n+1)^k \equiv 1 \pmod n$$ $$a_k \times (n+1)^k \equiv a_k \pmod n$$

$$a = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0$$ $$\equiv (a_m + a_{m-1} \cdots + a_0) \pmod n$$ $$a \equiv s \pmod n$$ Hence proved.

Claim 2: Another possible divisibility rule for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n-1$'. Let '$s$' denote the alternating sum of digits of '$a$' expressed in base '$n-1$' i.e. if $a = (a_ma_{m-1} \ldots a_0)_{n-1}$, $s = a_0 - a_1 + a_2 - \cdots + (-1)^{m-1}a_{m-1} + (-1)^m a_m$

Now $n|a$ if and only $n|s$. More generally, $a \equiv s \pmod{n}$

Example:

Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $12$.

$611 = 4 \times 12^2 + 2 \times 12^1 + B \times 12^0 = (42B)_{12}$

where $(42B)_{14}$ denotes that the decimal number $611$ expressed in base $12$, $A$ stands for the tenth digit and $B$ stands for the eleventh digit. The alternating sum of the digits $s = B_{12} - 2 + 4 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.

Proof:

The proof for this claim writes itself out just like the one above. Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n-1$'.

$a = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0$

Now, note that

$$n-1 \equiv (-1) \pmod n$$ $$(n-1)^k \equiv (-1)^k \pmod n$$ $$a_k \times (n-1)^k \equiv (-1)^k a_k \pmod n$$

$$a = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0$$ $$a \equiv ((-1)^m a_m + (-1)^{m-1} a_{m-1} \cdots + a_0) \pmod n$$ $$a \equiv s \pmod n$$ Hence proved.

-
The above is simplified if one exploits to the hilt the fact that radix notation has polynomial form. See my answer and its links for more on this viewpoint. Alas, the power of the lowly polynomial is often underappreciated. – Bill Dubuque Aug 15 '11 at 16:22