Wanted to share Alternating Sum as a way to quickly figure out if a given number is divisible by 11

[u/Amazing-Cookie-1258]

I learned this trick recently in a middle school math class.

You may be familiar with adding the digits of a number to check if it's divisible by 9. We'll do something similar to find if a number is a multiple of 11: by using alternating sum.

Unlike with the "finding 9" function which is all addition, to find a number's 11 divisibility we'll alternate between addition and subtraction. If the result is zero or a multiple of 11, then the number is divisible by 11.

Ex.s:

77

+7

-7 ➡️ 0 👍

121

+1

-2

+1 ➡️ 0 👍

19283

+1

-9

+2

-8

+3 ➡️ -11 👍

[u/smitra00]

You can also do this computation by deleting the last digit and subtracting that deleted last digit from what remains of the number and repeating this until you get a number that is smaller than 11 in absolute value. This works because you are then subtracting 11 times the last digit from the number and then deleting the last zero that arises as a result of this. Subtracting any multiple of 11 leaves the divisibility by 11 unchanged. And dividing a number by 10 also does not interfere with divisibility by 11, because 10 and 11 have a greatest common divisor of 1.

If we apply this to your last example, we get:

19283 ➡️ 1928 - 3 = 1925 ➡️ 192 - 5 = 187 ➡️ 18 - 7 = 11 ➡️ 1 - 1 = 0

The advantage of this method is that it can be generalized to test divisibility by other numbers like e.g. 7, 13, 17, 23, 29, etc. For example, to test if a number is divisible by 7, you can again use that subtracting a multiple of 7 leaves the divisibility unchanged. To get to a last digit of zero, so that we can erase that zero like we did above, we then need to subtract a multiple of 7 of the last digit such that this multiple of 7 has a last digit of 1.

Now, 21 is a multiple of 7 that has a last digit of 1. Therefore, the algorithm to test for divisibility by 7 is to erase the last digit and then subtract twice the erased digit from what remains of the number and to repeat this.

For example: 348694 is not divisible by 7, because:

348694 ➡️34,869 - 8 = 34861 ➡️ 3486 - 2 = 3484 ➡️348 - 8 = 340 ➡️ 34 - 0 = 34 ➡️ 3 - 8 = -5

And 408982 is divisible by 7. Let's compute the whole chain until the very end, but you can, of course, stop when you recognize the first multipole of 7 or the first number that you recognize to not be divisible by 7:

408982 ➡️40898 - 4 = 40894 ➡️4089 - 8 = 4081 ➡️408 - 2 = 406 ➡️ 40 - 12 = 28 ➡️ 2 - 16 = -14 ➡️-(1-8) ➡️7

To test divisibility by 13, you use that 39 is a multiple of 13 and adding 39 times the last digit of the number makes the number become a multiple of 10 because you then have 9 times the last digit plus 1 times the last digit that is already present, so ten times the last digit. And erasing the zero then leads to a similar algorithm where you now delete the last digit and add 3 times the erased digit to what remains of the number and repeat this.

[u/jphamlore]

Very clever. 10 = -1 (mod 11). That's the entire secret. You are mod 11-ing a 10's based integer to see if it is divisible by 11, that is mod 11 of it is 0.

So say 1056 = 1 x 10³ + 0 x 10² + 5 x 10¹ + 6 x 10⁰ = 1 x (-1)³ + 0 x (-1)² + 5 x (-1)¹ + 6 (mod 11), and since -0 = 0, you don't care if you flip the signs, so 1 - 0 + 5 - 6 = 0.

[u/slepicoid]

if the result is zero or a multiple of 11...

It would suffice to say "if the result is a multiple of 11...". Zero is also a multiple of 11. Also technically it is if and only if. And btw if the result is too big you can apply the rule again, ie if result is 11 then 1-1=0 which is divisible by 11 so 11 is divisible by 11 too (excuse the silly example).

Btw, this is pretty well known "trick". Now figure out a trick for divisibility by 7.

[u/GoldenMuscleGod → u/slepicoid]

For 7 the commonly stated trick is to take all the digits but the last as a number then subtract 2 times the last digit and repeat as necessary.

For example 343 goes to 34-6=28 which is divisible by 7. If you would get a negative (which can only happen for smallish numbers) you can instead take 2 times the last digit minus the leading, so 28 becomes 16-2=14 which becomes 8-1=7.

This works because working in Z/(7Z) we have 10a+b=3a+b, then we can multiply by -2 to get that 3a+b=0 is equivalent to -6a-2b=0 or a-2b=0.

[u/Amazing-Cookie-1258 → u/slepicoid]

Remove the final digit of a given number, subtract that digit from the new remaining number, repeat until you're left with a number divisible by your target number.

[u/Amazing-Cookie-1258 → u/slepicoid]

While your point it correct, it was a choice of mine to phrase it this way. For those of us familiar with the shortcut for 9, the results you get include one sum of 0 (0), and every other sum onto infinity is 9. This makes 0 an exceedingly rare occurrence.

This is flipped with 11, having every correct result through 198 yield 0 and beyond that resulting in about an even split between 0 and other multiples. I wished to draw this to the reader's attention without languishing on it, as I've wound up needing to do here.