Proof of divisibility by 11
Theorem:
Add all digits in the odd positions, and add all digits
in the even positions. If the difference of the sums is divisible by 11 then the
integer is divisible by 11.
Proof:
Suppose we have a number a2na2n-1a2n-2.....a2a1a0
with an odd number of digits. we will show that the integer is divisible by 11 if
(a2n - a2n-1 + a2n-2 - .... + a2
-
a1
+ a0) is divisible by 11.
The integer can be expanded as
a2na2n-1a2n-2 ....a2a1a0
= a2nx102n + a2n-1x102n-1
+ a2n-2x102n-2 + .... + a2x102
+ a1x10
+ a0
Now notice the facts that:
10 = 11 - 1 = 11k1 - 1
102 = (11 - 1)2 = 112 - 2x11 + 1 = 11k2
+ 1
103 = (11 - 1)3 = 113 - 3x112 + 3x11
- 1 = 11k3 - 1
104 = (11 - 1)4 = 114 - 4x113 + 6x112 -4x11 + 1 = 11k4
+ 1
....
102n-1 = 11k2n-1 - 1
102n = 11k2n + 1
Now we have
a2na2n-1a2n-2 ....a2a1a0
= a2nx102n + a2n-1x102n-1
+ a2n-2x102n-2 + .... + a2x102
+ a1x10
+ a0
= a2nx(11k2n + 1) + a2n-1x(11k2n-1 - 1) + a2n-2x(11k2n-2 + 1) + .... + a2x(11k2 + 1) + a1x(11k1 - 1) + a0
= 11a2nk2n + a2n + 11a2n-1k2n-1 - a2n-1 + 11a2n-2k2n + a2n-2 + .... + 11a2k2 + a2 + 11a1k1 - a1 + a0
= 11(a2nk2n + a2n-1k2n-1 + a2n-2k2n + .... + a2k2 + a1k1) + (a2n - a2n-1 + a2n-2 - .... + a2 - a1 + a0)
Since the term 11(a2nk2n + a2n-1k2n-1 + a2n-2k2n + .... + a2k2 + a1k1) is divisible by 11, the integer anan-1an-2 ....a1a0 is divisible by 11 if (a2n - a2n-1 + a2n-2 - .... + a2 - a1 + a0) is divisible by 11.