# Palindromes

• Feb 25th 2007, 06:13 PM
lyla
Palindromes
Any help would be appreciated on the following.

A palindrome is a number that reads same backwards as fowards (for instance, 373 and 521125 are palindromes). Prove that any palindrome with an even number of digits is divisible by 11.

• Feb 25th 2007, 06:50 PM
AfterShock
Quote:

Originally Posted by lyla
Any help would be appreciated on the following.

A palindrome is a number that reads same backwards as fowards (for instance, 373 and 521125 are palindromes). Prove that any palindrome with an even number of digits is divisible by 11.

Hi lyla,

Intuitively, this is obvious because you add and subtract each of the digits;

Lemma: If k is even, 10^(k) = 99....9 (even # of 9's = k) + 1
ex. k =2; 10^2 = 100 = 99 + 1
k = 4; 10^4 = 10000 = 9999 + 1

Lemma 2: if k is odd, 10^(k) = 10....01 (k-1 0's) - 1
ex. k = 3; 1000 = 1001 - 1
Which we know 1001 is div. by 11

Theorem: n = (a_k*a_(k-1)*...*a_2*a_1*a_0)_10; 11|n iff 11|summation[(-1)^(i)*a_i, from i = 0...k]

With the summation above, without loss of generality, a_k - a_(k-1) + a_(k-2) - ...

Proof: n = a_k*10^k + a_(k-1)*10^(k-1) + ... + a_2*10^2 + a_1*(10) + a_0

Note that a_2*10^2 = 99 + 1 and a_1*10 = (11 - 1), etc.
.
.
.
Thus, it should be obvious from this that just adding and subtracting consecutive terms will determine if the number is div. by 11. With palindromes, since you're adding and subtracting the same number of digits, it will = 0, and thus will be divisible by 11.

Q.E.D.
• Feb 25th 2007, 07:10 PM
ThePerfectHacker
Quote:

Originally Posted by lyla
Any help would be appreciated on the following.

A palindrome is a number that reads same backwards as fowards (for instance, 373 and 521125 are palindromes). Prove that any palindrome with an even number of digits is divisible by 11.