Divisibility by 11 for all palindromes with an even number of digits

  1. 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. jcsd
  3. lanedance

    lanedance 3,307
    Homework Helper

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

    so start with:
    [tex] 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 [/tex]

    so for this case it remains to show a_0(10^3+1) is divisible by 11...
     
  4. 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,
     
  5. HallsofIvy

    HallsofIvy 40,310
    Staff Emeritus
    Science Advisor

    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.
     
  6. thank you. and for a base k palindromic number, can I just substitute k for 10?
     
  7. 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.
     
  8. 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
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?