Give an algorithm that determines whether a given number is divisible by 11 or not. The number could have up to one million digits.

(Note that simply dividing by 11, or doing long division by 11 is not allowed as a solution.)

I learned this when I was a math tutor years ago. I do not know the proof, nor do I know if it's guaranteed to be correct; however, I have yet to find a contradiction.

Algorithm: Add up all digits in even positions to get a number, and add up all digits in odd positions to get another number. Subtract these two numbers and if the total is divisible by 11 then the original number is divisible by 11 as well. (Therefore, you may need to use the algorithm recursively.)

Examples:

135802467913580246790
Add up 1 + 5 + 0 + 4 + 7 + 1 + 5 + 0 + 4 + 7 + 0 = 34
Add up 3 + 8 + 2 + 6 + 9 + 3 + 8 + 2 + 6 + 9 = 56
Subtract 56 - 34 = 22 which as we know is divisible by 11, thus 135802467913580246790 is divisible by 11.

1234
Add up 1 + 3 = 4
Add up 2 + 4 = 6
Subtract 6 - 4 = 2 which is not divisible by 11 and so 1234 isn't either.

A quick Google search reveals an interesting page on this type of divisibility algorithms, and provides an algebraic proof at the end:
http://www.egge.net/~savory/maths1.htm

Interestingly, the algorithm for 11 is different (and easier!) than that which I've given. So... I wonder if anyone can prove or disprove the algorithm I've given above... :)

Posted by Kurious on 2008-01-02 17:46:02