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.

Printable View

- Sep 13th 2008, 03:02 PMrmpatel5divisible 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, 03:47 PMo_O
Let the digit representation of a number be: $\displaystyle d_{k}d_{k-1}d_{k-2}...d_{2}d_{1}d_{0}$

Note that it can be represented as: $\displaystyle 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:

$\displaystyle 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}$

.................................................$\displaystyle \equiv d_{0} - d_{1} + d_{2} - d_{3} + \hdots + (-1)^{k}d_{k} \ (\text{mod } 11)$

Hint: $\displaystyle 10^{k} \equiv (-1)^{k} \ (\text{mod 11})$ - Sep 13th 2008, 10:46 PMrmpatel5
- Sep 14th 2008, 08:49 AMo_O
What are you having trouble with? Do you understand the idea behind the earlier post?

Using the hint:

$\displaystyle 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)

.................................$\displaystyle \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 : $\displaystyle 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.