Suppose you have an integer and you want to find its remainder upon division by a positive integer . The obvious way is to just to divide by , but there may be easier ways to do this if you are only interested in the remainder, rather than the quotient. In particular, there are a lot of simple rules, which can be derived using modular arithmetic, that show that the remainder of in is the same as the remainder of in a smaller integer , where the value of can be easily computed from the digits of in a given base. For example, I would struggle to divide 5292 by 3 in my head, but I can find the remainder upon division by 3 in a few seconds by knowing the rule that the remainder of 3 in the sum of the decimal digits of 5292 will be the same: adding 5, 2, 9 and 2 gives 18, which is divisible by 3, so the remainder is 0. Let’s see what other rules like this we can find.

The task can be stated as follows. Suppose and are non-negative integers, and are positive integers, , , … and are integers such that for every integer such that , , and

(so the digits of in base are , , … and in that order). We want to find the remainder of in . As explained in the previous post, is congruent to modulo . That is,

Let be an integer congruent to modulo , such as the remainder of in (since only small bases are practically useful this should be easy to find). Then for every non-negative integer , is congruent to modulo by Theorem 2 from the previous post, and hence is congruent to by applying the same theorem. So, if we let

then it follows by Theorem 1 that is congruent to modulo , so is the remainder of in .

The smaller is, the better, because that makes it easier to find its remainder upon division by . Therefore, the best value of to choose is not necessarily the remainder of in : if this remainder is greater than then it would be better to choose as since will be less than . If can be chosen to be 0, 1 or is especially easy to compute.

If is 0 (which means divides ), then is 1, and for every positive integer , is 0, so we have

The least upper bound on the value of is , which is nice because does not depend on , so no matter how large is, the remainder of in will be just as easy to find.

This gives us the first divisibility rule.

Proposition 1If divides , then the remainder of in is the remainder of in (the last digit of in base ).

Consequently, divides if and only if it divides .

In base 10 in particular, this tells us that 2 divides if and only if is 0, 2, 4, 6 or 8, 5 divides if and only if is 0 or 5, and 10 divides if and only if is 0.

If is 1 (which means divides ), then for every non-negative integer , is 1, so we have

The least upper bound on the value of is now , which does depend on . However, if proves to be too large, we can simply repeat the process with in place of to get a smaller value of . It takes a very large value of to make too large, anyway, because as a function of , grows at a much slower rate than .

This gives us the second divisibility rule.

Proposition 2If divides , then the remainder of in is the remainder of in (the sum of all the digits of in base ).

Consequently, divides if and only if it divides .

In base 10 in particular, this tells us that 3 divides if and only if 3 divides , and 9 divides if and only if 9 divides .

If is (which means divides ), then for every non-negative integer , is 1 if is even and if is odd, so we have

This gives us the third divisibility rule.

Proposition 3If divides , then the remainder of in is the remainder of in (the alternating sum of all the digits of in base ).

Consequently, divides if and only if it divides .

As with the previous rule, it may be necessary to apply this rule repeatedly for large values of .

In base 10 in particular, this tells us that 11 divides if and only if 11 divides . For example, so 11 divides 12882.

Even outside of these three cases, the reduction to can still be helpful; it’s just that you now have to perform multiplications as well as additions and increases. For example, let’s try and find whether 1288 is divisible by 7. We choose because 10 is congruent to 3 modulo 7. Then we reduce the problem to finding out whether is divisible by 7, and of course it is. This would definitely be a useful strategy for a computer, but I don’t think I would have enough working memory to compute that sum in my head.

The existence of these rules can help us give an answer to which is the best base, although of course this is really a subjective question. Since it’s very easy to check for divisibility by if divides the base , it might seem best to choose a base with a high density of divisors, such as 6, 12 or 24. It would certainly be a bad idea to choose a prime number for a base. However, it is also useful to have a lot of integers such that divides or , since Propositions 2 and 3 give easy divisibility rules for such values of . So you shouldn’t necessarily rule out the prime bases—in fact, a prime base such that and have a lot of divisors may be better than a composite base such that and are prime.