Divisibility by base + 1

To test whether a number is divisible by 11, add every other digit together and subtract the rest of the digits. The result is divisible by 11 if and only if the original number is divisible by 11.

For example, start with n = 31425. Add 3, 4, and 5, and subtract 1 and 2. Since 3 + 4 + 5 - 1 - 2 = 9, and 9 is not divisible by 11, neither is 31425.

For another example, take 349041. We have 3 + 9 + 4 = 16, and 4 + 0 + 1 = 5, and 16 - 5 = 11. Since 11 is obviously divisible by 11, so is 349041.

The same trick that works for testing base 10 numbers for divisibility by 11 works for testing base 16 numbers for divisibility by 17. More generally, it works for testing base b numbers for divisibility by b+1.

Let m = b + 1. Then

which implies

Here a_n is the nth digit of a number in base b, numbering the digits from the least significant, counting from 0.

Sometimes a rule for testing divisibility by m will also tell you the remainder when a number is divided by m, but sometimes not. The method presented here will give you the remainder by b + 1, but only if you start adding up digits from the right end. Note in the proof that the digits in even positions (counting from 0) have a positive coefficient and the digits in odd positions have a negative coefficient.

For example, let's look at 1EDA86_hex in hexadecimal (base 16). If we add 6, A, and E, and subtract 8, D, and 1, we get 8, which is the remainder when 1EDA86_hex is divided by 11_hex (i.e. 17_ten). But if we add 1, D, and 8 and subtract E, A, and 8, we get 9.

You can start from either end of a number if you only want to test divisibility, not to compute a remainder. But if you do want the remainder, you might get the wrong result if you start at the wrong end.

Application: Divisibility by 7, 11, and 13

We can apply the technique above to test for divisibility by 1001 in base 1000. And why would we want to do that? Because 1001 = 7 * 11 * 13. Reducing a large number mod 1001 takes the problem of testing for divisibility mod 7, 11, or 13 down to the problem of testing 3-digit numbers.

Base 1000 is just base 10, thinking of triples of ordinary digits as a single base 1000 digit. If we write a number with thousands separators (i.e. commas in some countries, periods in others) then each segment is a base 1000 digit."

Example 1

For example, let's test whether n = 598,203,918 is divisible by 7, 11, or 13.

The alternating (base 1000) digit sum is

598 - 203 + 918 = 1313 = 13 * 101.

The result is clearly divisible by 13, so n is divisible by 13. But since 101 is not divisible by 7 or 11, neither is n.

Example 2

For another example, let n = 314,159,265,358 and find the remainders when n is divided by 7, 11, and 13. We start by reducing n mod 1001.

314159265358 = -314 + 159 - 265 + 358 = -62 = 939 mod 1001.

Now 939 = 1 = mod 7, so n = 1 mod 7.

Also, 9 + 9 - 3 = 15 = 4 mod 11, and so n = 4 mod 11.

Finally, 939 = 3 mod 13, so n = 3 mod 13.

The post Divisibility by base + 1 first appeared on John D. Cook.