Register to reply

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

by ripcity4545
Tags: mod, modular, modulo, palindrome
Share this thread:
ripcity4545
#1
May25-10, 06:19 AM
P: 17
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!
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
lanedance
#2
May25-10, 07:01 AM
HW Helper
P: 3,307
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...
ripcity4545
#3
May25-10, 07:48 AM
P: 17
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,

HallsofIvy
#4
May25-10, 08:13 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,340
Divisibility by 11 for all palindromes with an even number of digits

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.
ripcity4545
#5
May25-10, 08:34 AM
P: 17
thank you. and for a base k palindromic number, can I just substitute k for 10?
ripcity4545
#6
May25-10, 08:43 AM
P: 17
Quote Quote by ripcity4545 View Post
thank you. and for a base k palindromic number, can I just substitute k for 10?
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.
Martin Rattigan
#7
May25-10, 01:14 PM
P: 312
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.)


Register to reply

Related Discussions
Two successive digits and divisibility puzzle Fun, Photos & Games 1
Simple number theory, divisibility Linear & Abstract Algebra 23
Prime number divisibility Precalculus Mathematics Homework 2
Number Theory - divisibility and primes Calculus & Beyond Homework 1
Number of digits in n! Programming & Computer Science 8