A number is evenly divisible by 11 the alternating sum of its digits are divisible by 11 (including zero).
Example: 82,762,262 is divisible by 11 because:
8-2+7-6+2-2+6-2 = 11, which is divisible by 11.
The rule can also be applied this way: add the total of the odd digits (1st, 3rd, 5th, …) and subtract the total of the even digits (2nd, 4th, …)
(8+7+2+6) - (2+6+2+2) = 23 - 12 = 11
The site does not, however, provide a proof for this rule. I am preparing to teach these proofs to my Number Theory class, but I cannot remember (nor find for that matter) this particular proof.
The first thing is that 11 is a factor of 99. So if you take a number expressed in decimal notation, group the digits in pairs (AB,CD,EF,GH) then take the sum (AB+CD+EF+GH), it will have the same remainder divided by 99 as ABCDEFGH does – so it also has the samed remeinder when divided by 11. You can keep on doing that until you finish up with a two-digit number, say MN. Then if M=N, the original number was divisible by 11.
The A-B+C-D+E-F+G-H method just takes a short-cut through that whole process.
Giles has a good proof. Another proof is to note that 10x===-x(mod 11); so a number ABCD=1000A+100B+10C+D has the same remainder (modulo 11) as (B-A)CD=100(B-A)+10C+D. Repeating this, you get the alternating sum.
B-A might be negative, of course, so “(B-A)CD” might not be a standard decimal number; this is OK but may be confusing. You can fix this by working from the other end: ABCD and ABC0-D0=10(100A+10B+C-D) have the same divisibility by 11. Now of course the factor of 10 doesn’t matter (since 10 and 11 are relatively prime), so ABCD===ABC-D(mod 11). So now perform the subtraction and continue.
This idea extends, though obviously some numbers have more convenient rules than others. For 13, for example, you have 10x===-3x(mod 13), so ABCD and (B-3A)CD have the same divisibility. This is not so nice, but then repeating this step, also (9A-3B+C)D and (D-3C+9B-27A) have the same divisibility. Now 27===1(mod 13), so this is the same as (D-3C+9B-A); at least you don’t have to multiply by anything bigger than 10. Also if you like you can split this into odd and even sums, but then you have to subtract three times the tens-digits from the ones-digits.
Working from the other end, you can notice that 137=91, so x===-90x(mod 13). Also 133=39, so x===40x(mod 13). So ABCD===10*(ABC-9D)===10(ABC+4*D)(mod 13).
One simple proof (well, not really a rigorous proof in any sense of the word):
You have a number with digits a,b,c,d.
Multiplied by 11, it becomes a,a+b,b+c,c+d,d.
The odd digits sum to a+(b+c)+(d), and the even digits sum to (a+b)+(c+d).
This holds for any number of digits, not just four.
Or: 10 = -1 (mod 11), so 10[sup]n[/sup] = (-1)[sup]n[/sup] (mod 11). Hence a10[sup]n[/sup] + b10[sup]n-1[/sup] + c10[sup]n-2[/sup] + … = +/- (a - b + c - …) (mod 11). So, a number in decimal notation is divisible by 11 if and only if the alternating sum of its digits is.
Start with any number. If you add 11, you increment the 1s column by 1, and the 10s column by one. Subtracting either of those columns from the other yields zero. Zero is divisible by eleven.
Sometimes, you don’t just affect the 1s and 10s column. If, by adding eleven, you should spill over into another column (e.g. 99+11=110), you have also (that is, besides incrementing both the 1s and 10s column by 1) you decrement the 1s column by 9, decrement the 10s columns by 8, and increment the hundreds column by 1. Now look at the alternating digits… you’ve changed (9-1) in alternating digits compared to (8) in the other set of alternating digits. You can carry the logic forward to spillovers into the 1000s column (999+11=1010) and so on. And of course, multiplication is just short hand for repeated addition.
(This is a variant on the trick of adding all the digits, and if they are divisible by 9, then the original number was divisible by 9. Notice how 9 and 11 are both the same distance from the number ten, and how similar the trick is to divisibility.)
No, that’s not rigorous, but I think it can be made rigorous, and the result is a proof that I think could be followed even by non number-theoreticians. (Though the proof must necessarily be a bit longer for that reason–baby steps must be made explicit. And this is irrelevant to the OP’s purpose, since he’s teaching a number theory class anyway. But still, I present this in the interest of math fun.)
The following is still not fully rigorous, but I think it’s clear it can be made so.
Say you have a number …dcba (The … means there may be more digits than just the four I’ve mentioned.)
Thats … 1000d + 100c + 10b + a.
Multiplying by 11 you get
… 11000d + 1100c +110b +11a
which could be written as:
… dd000 + cc00 + bb0 + aa
What happens when you put these all in columns to add them up?
Unfortunately, the columns in the font this board uses don’t line up, but try to pretend:
…
dd000
cc00
bb0
aa
Say instead of adding these columns up in the usual fashion, you simply added each column up and wrote down the answer beneath in (i.e, without carrying.) You will get a list of five numbers, to wit, the numbers
d, d + c, c + b, b + a, a
(its clear that if our original number had had more than four digits, then the list I just typed out would not have an element reading “d” but rather “e + d” with another element previous to it with either an “e” (and that would begin the list) or else an “f + e” with yet another element previous to it, and so on. The comments I am going to make here generalize to all those cases.)
Now, say you determined yourself to add up the odd numbered numbers from this list (the 1st, 3rd, and 5th in this case) and subtract the even numbered ones from that total. You get
d - d - c + c + b - b - a + a.
In other words, zero.
So the list of numbers we got from the unorthodox column addition will always come to zero when adding the odd column results and subtracting the even column results.
But what about orthodox addition? In this case, those numbers on the list we got from unorthodox addition which have two digits will cause problems, because of carrying. If one of the numbers on the list had been 15, then if we had added in the orthodox fashion, we would have written down, not 15, but rather, 5 and carried the one over to the next column.
Do address that possibility, say we had, after unorthodox addition, come up with the following list of numbers:
z, y, x, w, u.
If any of these had two digits, then in orthodox addition the tens digit would have been carried. Notice that if any had two digits, the tens digit had to be a ‘1’. This is because, in each of the columns above, at most two non zero numerals appeared. The largest two digit number resulting from adding two one digit numbers is 18—the digit to be carried, therefore, is 1 at maximum.
So, say w had been a two digit number. Then the numeral for the answer to the addition problem (the numeral standing for the number we got by multiplying our original number by 11 in the first place) would consist in the following digits:
z, y, x + 1, w – 10, u.
Now, recall that z – y + x – w + u equaled 0. What does this new list add up to, then? Well, the x digit is an odd one, so it is added. The w digit is subtracted. So the new list adds up to z – y + (x + 1) – (w – 10) + u,
Or,
z – y + x + 1 – w + 10 + u
or
z – y + x – w + u + 10 + 1
or
0 + 11 == 11.
Had the carrying been done from x (an odd digit) to y (an even digit) instead, then the total would have been -11 rather than 11.
Either way, its clear a single carry changes the total by either -11 or 11. If there are multiple carries, then, they must cause the total to change by some number you can get from adding and subtracting 11’s. But, since we are adding and subtracting all these 11s from an “initial” total of zero, this just means the total must be some multiple of 11.
If I can hijack, there is a similar but not-as-well-known algorithm to show if a large number is divisible by 7, 11, or 13. Instead of adding/subtracting consecutive digits, add/subtract consectutive groups of three digits (starting with the least-significant group of three), and see if this number is divisible by 7, 11, 13.
Let’s use 2,133,059,994 as an example. Then 994 - 059 + 133 - 2 = 1066 Applying the algorithm again to this number gives 66 - 1 = 65. 65 = 13*5 is divisible by 13, but not by 7 or 11. Therefore 13 is a factor of 2,133,059,994, but 7 and 11 are not.
The reason this algorithm works is because 71113 = 1,001, and so if a is divisible by either 7, 11, or 13, (a mod 1001) should also be divisible by the same number. Proof then is similar to the proofs given above for the divisibility by 11.
1. Chop up the number into groups of 12 (twelve) digits, starting from the radix point.
2. Within each group, multiply the digits by these corresponding weights: 1, 11, 4, 5, 3, 7, 12, 2, 9, 8, 10, and 6. But do it all in base 11 of course.
These weights can be easily recalled by the mnemonic phrase: A grasshopper eats leeks, but accepts pomegranates if desperate; division encourages hunger.
3. Add up all the products. If the sum is large, repeat the above process on the sum.
4. Otherwise, see if the sum is divisible by 13. If it is, then voila, so was the original number! Base eleven, people. Let’s switch today.
Actually, as far as division rules go, 11 is not a bad choice for a base, because
11^2 - 1 = 120
and 120 is the smallest number with 16 different factors (including itself and 1). Each of those factors, including 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 30 and 60, has a fairly simple division rule.
Such pity that humans didn’t evolve to have 6 fingers on one hand and 5 on the other!
