Divisibility by 11

Date: 02/17/98 at 08:27:18
From: adorable
Subject: Divisibility

Dear Doctor Math:

I need your help in solving this problem.

Problem:  

   To check whether a number is divisible by 11, sum the digits in the
   odd positions counting from the left (the first, third, ....) and
   then sum the remaining digits. 
   If the difference between the two sums is divisible by 11, 
   then so is the original number. Otherwise it is not.
   Why does this work?

I have tried to work it out. My solutions are:

1) if the answer for the subtraction is 0, it is divisible. 
2) if the answer for the subtraction is not 0, it is not divisible.

Unfortunately, I am not able to know why it is possible and what can 
be done for the extension of this problem.

Thus I need your help.

Thank you,
Suria

Date: 02/17/98 at 19:58:54
From: Doctor Sam
Subject: Re: Divisibility

Suria,

The reason this works is because of a special relationship that 11 has 
with 10.  

What I mean is this. Any number written in our decimal system is made 
up of powers of 10. For example, 

   65,321 = 6(10^4) + 5(10^3)+3(10^2) + 2(10)+1. 

Now if you are interested in knowing whether 65,321 is a multiple of 5 
(that is, is exactly divisible by 5), you can tell just by looking 
at the last digit. That's because 10^4, 10^3, 10^2, and 10 are all 
divisible by 5, so the last digit on the end gets to cast the deciding 
vote.

Deciding whether 65,321 is a multiple of 3 is a little harder, since 
no power of 10 is a multiple of 3.  But 

         10 =  9   + 1 and
        100 = 99   + 1 and 
       1000 = 999  + 1 etc.

So if you had 65,321,

     65,321 = 6(10^4) + 5(10^3)+3(10^2) + 2(10)+1

you could rewrite this as

     65,321 = 6(9999+1) + 5(999+1) + 3(99+1) + 2(9+1)+1
            = 6(9999) + 5(999) + 3(99) + 2(9) + (6+5+3+2+1)

The first part is divisible by 3 so 65,321 is a multiple of 3 if the 
sum of its digits 6+5+3+2+1 is divisible by 3.

Now we are ready for 11.

Eleven is a little more complicated, but look at this neat pattern:

99                is a multiple of 11
9999              is a multiple of 11
999999            is a multiple of 11
...
any even number of 9's makes a multiple of 11.

If you look at how we wrote 
   
     65,321 = 6(9999+1) + 5(999+1) + 3(99+1) + 2(9+1) + 1

you can see that every other term contains a number that is a multiple 
of 11.  Unfortunately, numbers with an odd number of 9's are not 
divisible by 11.

But look at this pattern for these numbers:

10 = 10^1       = 11 - 1
1000 = 10^3     = 1001 - 1
100000 = 10^5   = 100001 - 1
10000000 = 10^7 = 10000001 - 1

and each of these numbers: 11, 1001, 100001, 10000001, ... is a 
multiple of 11. (Check it out by long division . . . it's worthwhile 
looking at the pattern you get when you divide 1 00 00 00 00 00 1 by 
11!)

Back to the example of 65,321.

    65,321 = 6(9999+1) + 5(1001 - 1) + 3(99+1) + 2(11-1) + 1

           = 6(9999) + 6 + 5(1001) - 5 + 3(99) + 3 + 2(11) - 2 + 1

All the terms with parentheses are multiples of 11. So 65,321 will 
be divisible by 11 if the remaining numbers are a multiple of 11. 
That is,
              6 - 5 + 3 - 2 + 1

Just the numbers you spoke about in your letter.

In general, the numbers in the odd positions are part of the "multiple 
of 999...999 + 1" and so are added to the total. The numbers in the 
even positions are part of the multples of "1000...0001 - 1" and so 
get subtracted.

The final test is to look at this alternating sum and difference of 
digits. But the result does not have to be 0 in order to be a multiple 
of 11...ANY multiple of 11 will do. For example,  

         8030209 gives 8 + 3 + 2 + 9 = 22.  

Since 22 is a multiple of 11, so is 8,030,209.

I hope that helps.

-Doctor Sam,  The Math Forum
 Check out our Web site http://mathforum.org/dr.math/