Reduction Rules

Now, as you've probably noticed, these things that I've been calling divisibility tests are not really divisibility tests at all, they're rules for reducing a number to a smaller one that is congruent to the first modulo some number m. The reduction doesn't affect divisibility by m, so it provides a way of turning a hard divisibility problem into an easier one, but still, the reduction and the test are completely different things.

As a result, you don't have to reduce once and then test, you can reduce as many times as necessary (although in practice twice is almost always sufficient). If, for example, you want to test whether 538 is divisible by 9, traditionally you'd reduce 538 to 16, and then reduce 16 to 7.

Another thing you can do is leave out the divisibility test and use the reduction as an efficient way of computing n mod m. Before I talk about that, though, I ought to say a few words about what I mean by “n mod m”.

If you're a math person, “n mod m” doesn't make any sense. You don't ever think about a single number mod m, you think about two numbers being congruent mod m. Eighteen, for example, is congruent to zero mod 9, but there's nothing special about zero; eighteen is also congruent to twenty-seven mod 9. You might choose a system of representatives of the different congruence classes mod m, and the representatives might be the numbers [0,m−1], but they might also be the numbers [1,m], or something else entirely.

If you're a computer person, however, “n mod m” makes perfect sense. That's how you read the expression n % m; and the value of that expression is just a number, the remainder on division of n by m. (I like the symbol, by the way … the slash in the percent sign correctly suggests that n % m is related to n / m.)

So, when I say “n mod m”, basically what I mean is n % m. That's a pretty good definition. It's simple, and it's consistent with the mathematical usage, since n % m is congruent to n mod m. There's just one little problem: it invariably does the wrong thing with negative numbers! I have, on occasion, wanted to compute n mod m for negative n, and every time it has been because I wanted to know the congruence class of n, not the remainder on division. In other words, it's true that −9 leaves remainder −2 when divided by 7, but it's true and useful that −9 is congruent to 5 mod 7.

So, when I say “n mod m”, what I really mean is the number in the range [0,m−1] that identifies the congruence class that n belongs to. In practice, however, I'm going to avoid the whole issue by not talking about negative numbers any more. As a result, if you're going to be working with negative numbers, you'll need to decide what definition you want to use and then make minor adjustments to the discussion as appropriate.

Now I'll get back to the point: how to use reduction rules to compute n mod m.

In the simplest case, there's almost nothing to it. If you add up the digits in a number, repeatedly, you'll end up with a number in the range [1,9] that is congruent to the original number mod 9. So, all you need to do is look at the result and, if it's 9, replace it with 0, and you're done.

Unfortunately, for almost any other reduction rule, the range of possible results is much larger than the number of congruence classes, even after the rule is applied repeatedly. If you're working mod 13, for example, you can use the rule {3,−1} to reduce 123456 to 333 (as we saw earlier), but then you're stuck. So, in most cases, computing n mod m is a two-step process.

1. Apply the reduction rule repeatedly.
2. Fiddle around with the result somehow to bring it into the range [0,m−1].

Here are some possibilities for that second step.

• Apply a different rule with a smaller value of k. For m = 13, for example, you could use the rule {1,−3}, which ordinarily is a bit of a nuisance but isn't too bad for three-digit numbers. As a more practical example, for m = 11 you could add the digits in pairs ({2,1}) and then subtract the two digits in the result ({1,−1}). Then, of course, you'd need to add 11 if the result turned out to be negative, which just goes to show that more fiddling might be necessary.
• Perform long division and take the remainder. If you're trying to do the calculation in your head, I recommend not keeping track of the quotient—for me, that one saved register is enough to change a slow and error-prone calculation into a quick and reliable one.
• Add and subtract shifted multiples of m. Starting from 333, for example, you might know that 26 is a multiple of 13, and so subtract 260, leaving 73, then subtract 52 to get 21, and finally subtract 13 to get the answer, 8. If you like, you can think of this as doing long division while not keeping track of the quotient and not always subtracting the correct multiple. (You might use an incorrect multiple because you don't know the correct one, or perhaps because the math is easier.)

Now that I've said all that, I have to admit that nowadays I don't use reduction rules to compute n mod m. Adding and subtracting multiples is just as easy, and you don't have to remember any rules to do it. I still use {1,1} for m = 3 or 9, just because it's so easy and familiar, and I might use {2,2} for m = 7 or {2,1} for m = 11 under some conditions, but that's about it.

Just as an example, here's the full train of thought for how I'd actually compute 123456 mod 13. Hmm … 123 is close to 130, but not quite there. The next multiple down is 130 − 13 = 117; that works, so subtract that to get 6456. Then, 64 is very close to 65, so subtract that to get −44 (the second complement of 56). Then just add 52, and there's the answer, 8.

Speaking of things that can replace reduction rules, here's something else that I discovered recently: if you can factor a number quickly (see Primes), you can immediately answer any question about divisibility. Is 299 divisible by 7? No, because it's 13 × 23. In theory you can even compute n mod m using factors, by taking the factors mod m and then multiplying them back together, like so, …

299 = 13 × 23 ≡ −1 × 2 = −2 ≡ 5 mod 7

… but in practice adding and subtracting multiples is much easier.

On the other hand, there's at least one thing that reduction rules are still good for, which is that you can use them to check your arithmetic. It's especially easy to check mod 9 … that's the method of casting out nines that apparently used to be taught in schools. I never learned it, myself, so I don't do it. That's all I'm going to say about that, but if you'd like further reading, here are some starting points.

Casting Out Nines to Check Arithmetic
Casting Out Nines and Elevens
Casting Out Nines (slightly more technical)

The article about casting out elevens points out that that method can detect transpositions. That's nice, since transpositions are a common error; it also reminds me of how credit card numbers and UPC numbers have check digits that allow transpositions to be detected … but that's another subject for another time.