Divisibility

Many people know about testing numbers for divisibility by 3 or 9: you add the digits and if (and only if) the sum is divisible by 3, so is the original number; if (and only if) the sum is divisible by 9, so is the original number. Not as many people know how to prove that, though. There are a number of ways, but one comes out of an easy procedure to create divisibility tests for other numbers, as follows.

Is 38752 a multiple of 7? We can write that number as 10 x 3875 + 2. More generally, if we have some number a we want to test, we can write it as a = 10b + c, where b is a with its last digit truncated, and c is the last digit of a. Now, it won’t change the divisibility by 7 if we add a multiple of 7, so let’s add 49c. We get a + 49c = 10b + 50c = 10(b + 5c). Nor will it change the divisibility by 7 if we divide by something that’s not a multiple of 7, namely 10. So a is divisible by 7 if and only if b + 5c is. In words, take the last digit of a, multiply by 5, and add it to the remaining digits; if and only if that’s a multiple of 7, then so is a. For example: 38752 becomes 3875+5×2 = 3885. We can do it again: 3885 becomes 388+5×5 = 413; and again: 413 becomes 41+5×3 = 56. We can stop here, we know 56 is a multiple of 7, so 38752 is too.

We could also subtract a multiple of 7 from a: a–21c = 10b–20c = 10(b–2c), from which we see a is a multiple of 7 if and only if twice the last digit subtracted from the rest of the number is. So 38752 becomes 3871, then 385, then 28, a multiple of 7.

You can come up with similar divisibility tests for any prime except 2 or 5, or in fact any number which is relatively prime to 10 (that is, any number whose last digit is 1, 3, 7, or 9). 11, for instance: adding 99c to a gives us an “addition coefficient” of 10, meaning you can test for divisibility by 11 by adding 10 times the last digit to the rest of the number; or subtract 11c to derive a “subtraction coefficient” of 1 — test by subtracting the last digit from the rest. 82115 becomes 8206 becomes 814 becomes 77, so 82115 is a multiple of 11.

The general recipe is, to derive addition and subtraction tests for divisibility by a number n ending in 1, 3, 7, or 9, multiply n by 9, 3, 7, or 1, respectively, and add 1 and divide by 10 to get the addition coefficient; multiply by 1, 7, 3, or 9, respectively, and subtract 1 and divide by 10 to get the subtraction coefficient. (Or use the fact that the addition and subtraction coefficients sum to n.)

You can do the same thing with more digits, although in most cases you probably wouldn’t want to. But, for instance, for divisibility by 11 you can write a = 100b + 10c + d, add 99(10cd) to get 100(b + (10cd)), and derive the test: Add the last two digits to the rest of the number, and if the result is divisible by 11, then so is the original. (82115 becomes 836 becomes 44, with fewer steps than before.)

For both 3 and 9 the 1-digit addition coefficient is 1, meaning that if you add the last digit to the rest of the number, the result has the same divisibility by 3 or 9. Clearly this implies if you add all the digits together the result has the same divisibility by 3 or 9 — proving the well known rules.

Advertisements