divisibility tests

there are lots of quick divisibility tests for small numbers. the most basic ones are divisibility by 2, 5 and 10 in base 10 numbers, because a quick glance at the last digit will tell you if it is divisible. the second most basic is divisibility by 3, which requires adding all the digits together and seeing if the sum is divisible by 3. the next tier of tests involves multiplying the last digit by some constant and adding it to the other digits.

using other bases can make divisibility tests easier. for example, in any base if the last digit is zero the number is divisible by the base. and the prime factors of the base can be tested for by examining the last digit, as 2 and 5 in base 10. on computers, numbers are represented in binary, but they can easily be converted to any base which is a power of two. any number can easily be tested for divisibility if some multiple of the number is one less than the base, by simply adding all the digits.

this leads to two novel results. just as divisibility by 9, and its factor 3, are easily tested in base 10, divisibility by 7 is easily tested in base 8 by adding the octal digits because 7 is one less than 8. similarly, in base 100 (which is base 10 taken two digits at a time) divisibility by 11 is easily tested.

take for example the number 10741474139 to test for divisibility by 11. adding pairs of digits gives us 01+07+41+47+41+39 = 176 = 01+76 = 77 which is clearly divisible by 11. again, this works because 99, a multiple of eleven, is one less than our base of 100.

for computers, obviously any power of two is easily checked by examining the last few bits. for the next easiest tier, a well chosen bit size makes testing for divisibility as easy as adding together well chosen digits. as mentioned above, choosing digits of 3 bits makes 7 an easy test. because 3*5*17 is 255, 8 bit digits make tests for those primes as easy as adding bytes with a final modulus.

for other values, where the inverse of the base modulo the divisor is not one, the inverse needs to be multiplied by each last digit as it is added to the word. I have never seen a definition of how to calculate those special last digit multipliers that you see all over the place, so here goes.

given divisor D in base B, calculate X, the inverse of the base modulo the divisor. now take the number N to be tested and add the last digit multiplied by X to the other digits repeatedly.

N1 = N0/B + (N0%B)*X
repeat

for example, given a base of 10 when testing for divisibility by 7, find the inverse 5 such that 5*10 is 1 mod 7. now given a number N such as 1449, repeatedly take the last digit, multiply it by 5, and add it to the other digits.

1449, 144 + 9*5
189, 18 + 9*5
63, 6 + 3*5
21, 2 + 1*5
7 (after this it repeats 7,35,28,42,14,21,7)

of course, you can stop at any step in which it is obvious the number passes or fails the divisibility test. Also, at any step, you can subtract instead of adding. when adding multiply by 5, but when subtracting multiply by 7-5=2. Using the example above, but subtracting in the second step, gives us this.

1449, 144 + 9*5
189, 18 - 9*2
0 (always a positive result for divisibility test)

mathematically, you multiply the remainder of the base division by either X or X-D (which is negative) before adding it to the quotient of the base division.