Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. May 25, 2010 #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. May 25, 2010 #2

    lanedance

    User Avatar
    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. May 25, 2010 #3
    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. May 25, 2010 #4

    HallsofIvy

    User Avatar
    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. May 25, 2010 #5
    thank you. and for a base k palindromic number, can I just substitute k for 10?
     
  7. May 25, 2010 #6
    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. May 25, 2010 #7
    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 this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Divisibility by 11 for all palindromes with an even number of digits
  1. 11 divisibility proof (Replies: 2)

Loading...