1
$\begingroup$

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$

4 Answers 4

3

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?

2

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

  • 1
    @Gerry Myerson: Well, yes, but that's a known result. :) (In fact, I just linked to a proof.)2011-08-15
2

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.

See also the closely related question.

0

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.

  • 0
    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.2011-08-15