Divisiblity Tests

I describe a method to generate a divisibility test for the divisor 13.

For a dividend B, express B in terms of its digits, i.e,
B = 10X + Y , where Y is the ones digit and X are the digits left of Y.

Working in modulo 13, if B is divisible by 13, then
10X + Y ≡ 0 .

We then propose a divisibility test that uses X and Y to check the divisibility. We propose
X - KY ≡ 0 ,
meaning that we subtract K times Y from the X digits and test whether 13 divides it.

Manipulating and substituting,
10KY + Y ≡ 0 => (10K+1) ≡ 0 .

Solving the equation, we obtain a value of K = -4. Hence, to test whether a number is divisible by 13, we take the ones digit, multiply it by 4 and add it to the digits on the left. If the result is divisible by 13, then the number is divisible.

To demonstrate the use of the test, let us test the numbers 1234, 2468, and 1781. For 1234, 123 + 4*4 = 139, which is clearly not divisible by 13. Hence, 1234 is not divisible by 13. For 2468, 246 + 4*8 = 278. We can recur the test, 27 + 4*8 = 59, and hence 2468 is not divisible by 13. Lastly, for 1781, 178+4 = 182, 18 + 4*2 = 26. Hence, 1781 is divisible by 13.

The method for generating the divisibility test is general, and can be extended to other numbers. However, for larger numbers, it might be necessary to compute the tens and hundreds digits (and increasingly higher powers of ten), so it might not be feasible for very large numbers.

As a last note, divisibility tests are useful for trivial tasks such as prime factorization using your head.