How to compute remainders in your head, and why prime bases aren’t such a bad idea

Suppose you have an integer {n} and you want to find its remainder upon division by a positive integer {m}. The obvious way is to just to divide {n} by {m}, 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 {m} in {n} is the same as the remainder of {m} in a smaller integer {n'}, where the value of {n'} can be easily computed from the digits of {n} 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 {n} and {k} are non-negative integers, {b} and {m} are positive integers, {d_0}, {d_1}, … and {d_k} are integers such that for every integer {i} such that {0 \le i \le k}, {0 \le d_i < b}, and

\displaystyle n = d_0 + d_1 b + \dotsb + d_k b^k

(so the digits of {n} in base {b} are {d_k}, {d_{k - 1}}, … and {d_0} in that order). We want to find the remainder {r} of {m} in {n}. As explained in the previous post, {r} is congruent to {n} modulo {m}. That is,

\displaystyle r \equiv d_0 + d_1 b + \dotsb + d_k b^k \mod m.

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

\displaystyle n' = d_0 + d_1 s + \dotsb + d_k s^k,

then it follows by Theorem 1 that {n'} is congruent to {r} modulo {m}, so {r} is the remainder of {m} in {n'}.

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

If {s} is 0 (which means {m} divides {b}), then {s^0} is 1, and for every positive integer {i}, {s^i} is 0, so we have

\displaystyle \begin{array}{rcl} n' &=& d_0 \cdot 1 + d_1 \cdot 0 + \dotsb + d_k \cdot 0 \\ &=& d_0 + 0 + \dotsb + 0 \\ &=& d_0 \mod m. \end{array}

The least upper bound on the value of {n'} is {b - 1}, which is nice because {b - 1} does not depend on {n}, so no matter how large {n} is, the remainder of {m} in {n'} will be just as easy to find.

This gives us the first divisibility rule.

Proposition 1 If {m} divides {b}, then the remainder of {m} in {n} is the remainder of {m} in {d_0} (the last digit of {n} in base {b}).

Consequently, {m} divides {n} if and only if it divides {d_0}.

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

If {s} is 1 (which means {m} divides {b - 1}), then for every non-negative integer {i}, {s^i} is 1, so we have

\displaystyle \begin{array}{rcl} n' &=& d_0 \cdot 1 + d_1 \cdot 1 + \dotsb + d_k \cdot 1 \\ &=& d_0 + d_1 + \dotsb + d_k \mod m. \\ \end{array}

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

This gives us the second divisibility rule.

Proposition 2 If {m} divides {b - 1}, then the remainder of {m} in {n} is the remainder of {m} in {d_0 + d_1 + \dotsb + d_k} (the sum of all the digits of {n} in base {b}).

Consequently, {m} divides {n} if and only if it divides {d_0 + d_1 + \dotsb + d_k}.

In base 10 in particular, this tells us that 3 divides {n} if and only if 3 divides {d_0 + d_1 + \dotsb + d_k}, and 9 divides {n} if and only if 9 divides {d_0 + d_1 + \dotsb + d_k}.

If {s} is {-1} (which means {m} divides {b + 1}), then for every non-negative integer {i}, {s^i} is 1 if {k} is even and {-1} if {k} is odd, so we have

\displaystyle \begin{array}{rcl} r &\equiv& d_0 \cdot 1 + d_1 \cdot (-1) + \dotsb + d_k \cdot (-1)^k \\ &\equiv& d_0 - d_1 + \dotsb + (-1)^k d_k \mod m. \\ \end{array}

This gives us the third divisibility rule.

Proposition 3 If {m} divides {b + 1}, then the remainder of {m} in {n} is the remainder of {m} in {d_0 - d_1 + \dotsb + (-1)^k d_k} (the alternating sum of all the digits of {n} in base {b}).

Consequently, {m} divides {n} if and only if it divides {d_0 - d_1 + \dotsb + (-1)^k d_k}.

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

In base 10 in particular, this tells us that 11 divides {n} if and only if 11 divides {d_0 - d_1 + \dotsb + (-1)^k d_k}. For example, {1 - 8 + 8 - 2 + 1 = 0} so 11 divides 12882.

Even outside of these three cases, the reduction to {n'} can still be helpful; it’s just that you now have to perform multiplications as well as additions and {n'} increases. For example, let’s try and find whether 1288 is divisible by 7. We choose {s = 3} because 10 is congruent to 3 modulo 7. Then we reduce the problem to finding out whether {8 + 8 \cdot 3 + 2 \cdot 3^2 + 1 \cdot 3^3 = 8 + 24 + 18 + 27 = 77} 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 {m} if {m} divides the base {b}, 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 {m} such that {m} divides {b - 1} or {b + 1}, since Propositions 2 and 3 give easy divisibility rules for such values of {m}. So you shouldn’t necessarily rule out the prime bases—in fact, a prime base {b} such that {b - 1} and {b + 1} have a lot of divisors may be better than a composite base {b} such that {b - 1} and {b + 1} are prime.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s