How do divisibility tests work?
--[reporting2] Doing 'do snippet' - should be imbed--Tests of divisibility
There are some quick ways to test for whether a number is divisible by another number. To check if a number is divisible by n try these tests:
| n | a number is divisible by n if |
| 2 | If the last digit is even |
| 5 | If the last digit 0 or 5 |
| 4 | it ends e0, e4, e8, o2, o6 (e=even digit, o=odd digit)
or, if the last digit plus twice the second-to-last digit is divisible by 4 |
| 3 | If the sum of all of the digits is divisible by 3 |
| 6 | If the sum of all of the digits is divisible by 3 and the number is even |
| 8 | the last digit + 2 x the second-to-last digit + 4 x the third-to-last digit is divisible by 8 |
| 9 | If the sum of all of the digits is divisible by 9 |
| 11 | Make two sums of the alternate digits. For example, for the number 2453 the sums are 2+5=7 and 4+3=7. If the difference between the two sums is divisible by 11. |
Unfortunately, there is no easy test for 7.
They work because of modular arithmetic.
ab mod n = (a mod n)(b mod n) mod n
For example, If a number n has digits abcd then
n=a.103+b.102+c.101+d
Now we put the two facts together, substituting 10 modulo the number we are testing.
If we want to test for divisibility by 3 or 9 then we use 10 mod 3 or 10 mod 9. Both of these are 1, which means that all powers of 10 are equal to 1 modulo 3 or 9.
Hence n mod 3 = a+b+c+d mod 3 and
Hence n mod 9 = a+b+c+d mod 9.
To test for divisibility mod 11 we do the same thing. This time, 10 mod 11 is 10 but it is also the same as -1 mod 11. This is where the rule comes from: all the digits in an odd position must be multiplied by -1, and those in an even position by +1.
To test for divisibility by 4, note that 1 mod 4 = 1 and 10 mod 4 = 2. All higher powers of 10 are 0 mod 4. So we just need to add the last digit plus twice the second to last. The test for 8 is similar.