# divisible by 11 proof

• Sep 13th 2008, 04:02 PM
rmpatel5
divisible by 11 proof
Prove that a positive integer n is divisible by 11 if and only if the integer obtained by alternately adding and subtracting its digits beginning with adding the units digit and working to the left is divisible by 11.
• Sep 13th 2008, 04:47 PM
o_O
Let the digit representation of a number be: $d_{k}d_{k-1}d_{k-2}...d_{2}d_{1}d_{0}$

Note that it can be represented as: $d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}$

So all you have to show is that:
$d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}$
................................................. $\equiv d_{0} - d_{1} + d_{2} - d_{3} + \hdots + (-1)^{k}d_{k} \ (\text{mod } 11)$

Hint: $10^{k} \equiv (-1)^{k} \ (\text{mod 11})$
• Sep 13th 2008, 11:46 PM
rmpatel5
Quote:

Originally Posted by o_O
Let the digit representation of a number be: $d_{k}d_{k-1}d_{k-2}...d_{2}d_{1}d_{0}$

Note that it can be represented as: $d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}$

So all you have to show is that:
$d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}$
................................................. $\equiv d_{0} - d_{1} + d_{2} - d_{3} + \hdots + (-1)^{k}d_{k} \ (\text{mod } 11)$

Hint: $10^{k} \equiv (-1)^{k} \ (\text{mod 11})$

I have tired to do this for the past 1 hr and still cant mange to get the right answer!! Any more hints?
• Sep 14th 2008, 09:49 AM
o_O
What are you having trouble with? Do you understand the idea behind the earlier post?

Using the hint:
$d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}$ (1)

................................. $\equiv d_{0} + d_{1}(-1) + d_{2}(-1)^2 + d_{3}(-1)^3 + \hdots + d_{j}(-1)^{j} + \hdots d_{k}(-1)^{k} \ (\text{mod } 11)$ (2) for some j : $0 \leq j \leq k$

You can see that every second term is negative, giving us the alternating sum you wanted. So every integer is congruent to the alternating sum of its digit (mod 11). So if a number was divisible by 11, then their alternating sum (2) must be congruent to 0 (mod 11) which would mean (1) is congruent to 0 mod 11 which by definition, means that it is divisible by 11.