# Homework Help: Divisibility by 11 for all palindromes with an even number of digits

1. May 25, 2010

### ripcity4545

1. The problem statement, all variables and given/known data

Prove that every palindromic integer N in base 10 with an even number of digits is divisible by 11.

Then prove that every palindromic integer in base k with an even number of digits is divisible by k+1.

2. Relevant equations

palindromic means the number reads the same forwards and backwards

3. The attempt at a solution

I tried a general representation of a palindromic integer with even digits of form

D1*10^(2n-1) + D2*10^(2n-2) + ... +Dn * 10^n + Dn * 10^(n-1) +...+ D2*10^1 +D1*10^0

which makes the number N equal to

N= D1[10^(2n-1) + 10^0] + D2 [10^(2n-2) + 10^1] +...+Dn[10^n + 10^(n-1)].

But I can't figure out how to prove divisibility by 11. Thanks for any help!

2. May 25, 2010

### lanedance

how about starting with a low form & seeing if you can generalise from there....

$$10^3 a_0 + 10^2 a_1 + 10^1 a_1 + a_0 = (10^3+1)a_0 + (10^2+10)a_1 = (10^3+1)a_0 + 10 (11)a_1$$

so for this case it remains to show a_0(10^3+1) is divisible by 11...

3. May 25, 2010

### ripcity4545

Okay, thanks. I think I figured it out in base 10 by proving that you can factor out
(10^p +1) from each term, where p is some odd power, and then I proved by induction that

10^(2n-1) +1 is divisible by 11.

Any ideas on the general base n case? I can see that it works, just by using examples:

some palindrome in base 16 with 6 digits is divisible by 17:
10*16^5 + 12*16^4 + 3*16^3 + 3*16^2+12*16^1 + 10*16^0 = 11285450 = 17 * 663850.

but I have never done a proof like this for base n. Thanks,

4. May 25, 2010

### HallsofIvy

Since the number has an even number of digits, let n be half the digits and prove by induction on n.

If n= 1, the number is of the form aa= a(11).

Suppose any palindromic number with 2k digits is divisible by 11. let X be a palindromic number with 2k+ 2 digits. Let a be the leading digit (and so the ones digit). We can write X= a102k-1+ M + a where M is now a palindromic number with k digits.
X= a(102k-1+ 1)+ M. M is divisible by 11 by the inductive hypothesis and 102k-1+ 1 is divisible by 11 because, for m odd, xm+ 1= (x+1)(xm-1- xm-2+ ... + x- 1.

5. May 25, 2010

### ripcity4545

thank you. and for a base k palindromic number, can I just substitute k for 10?

6. May 25, 2010

### ripcity4545

nope, that doesn't work. I am definitely stuck on proving that a base k palindromic number with even digits is divisible by k+1.

7. May 25, 2010

### Martin Rattigan

Write down what the palindromic number means in base k. Express it modulo k+1. (Note that k is simply expressed modulo k+1.) You should finish up with 0 modulo k+1 if the number is to be divisible by k+1. (This includes 11 for base 10 as a special case of course.)

(If that isn't too clear just say so, and I'll expand it a bit.)

Last edited: May 26, 2010