Home> urticator.net Search About This Site > Domains Glue Stories Computers Driving Games Humor Law Math > Numbers Science Powers and Fractions Notes About Squares Decimal Expansions Repeat Length Again Number Maze Primes > Divisibility Intrinsic Nature of Primes Other Topics Other Topics (2)
In Other Bases 
Reduction RulesNow, 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 twentyseven mod 9. You might choose a system of representatives of the different congruence classes mod m, and the representatives might be the numbers [0,m1], 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,m1] 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 twostep process.
Here are some possibilities for that second step.
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 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.

See AlsoNext Block, The Other Methods Standard Series, The @ July (2004) 