Other Methods

1. Division, a.k.a. long division.
2. Pseudo-division, which is the same as division except that you don't keep track of the quotient. This method and the next are discussed briefly in the essay Reduction Rules.
3. Modulation, which is a method of adding and subtracting shifted multiples of m. The made-up name is meant to suggest that you're working modulo the number m.
4. Reduction rules. The method of casting out nines is one such rule. These are mentioned in Reduction Rules, but ironically the real discussion is in the previous essay, Divisibility.
5. Combined reduction rules. I talked about these in Four Digits, but called them combined divisibility tests, for the same reason that I started out calling reduction rules divisibility tests. For a single number m, a combined rule is no better than a standard rule; the advantage is that the rule applies to several numbers m at once.
6. Factorization. The idea here is that if you know all the factors of a number, you also know what numbers it's divisible by. This method is mentioned in Reduction Rules, too.
7. Pseudo-factorization, which is the same as factorization except that you don't keep track of factors of 2, 3, and 5 (“235s”). Of course, that only works if the number or numbers m you're interested in don't have any 235s … if, for example, they're prime numbers (other than 2, 3, and 5).
8. Backward modulation. This method combines pseudo-factorization and modulation. I haven't explained it anywhere else, so I guess I'll have to go into detail here.

   The problem with factorization and pseudo-factorization is that, in general, factoring numbers is hard. The technique I described in Primes and subsequent essays makes factoring easy, but only for “small” numbers and numbers that have lots of 235s. So, if I want to know if 60435 is divisible by 77, that's easy, …

   60435   12087   4029   1343   17×79   no

   … but if I want to know if 60434 is divisible, that's hard.

   60434   30217   hrm

   But, this is exactly where modulation comes in: if I get stuck in factoring, I can subtract a multiple of m instead, and then go back to factoring, like so.

   

   As in the previous example, the process terminates when I recognize the number … in this case, 143 = 11×13.

   Technically, I ought to write 30217 − 77 = 30140, but then that final zero is the first thing that's going to go away when I start removing 235s.

   I call the process backward modulation because it operates from right to left instead of from left to right. There are two reasons that's a good idea. First, it makes the process slightly faster, because removing 235s is faster than modulation; second, it makes the process much easier, because—surprise—the only multiples involved are m and 3m!

   How does that work? Well, once all the 235s have been removed, there are only four digits that a number can end with; and all four possibilities can be handled by either addition or subtraction of either m or 3m. Just for fun, here's an example that shows two more of the possibilities for 77.

   

   One last point: with practice, I think one could learn to drop the last digit before adding or subtracting. Then, for example, instead of 82943 + 77, one could do the much simpler sum 8294 + 8.

9. Elimination. As part of my technique for factoring, I memorized a bunch of products; and now, for certain combinations of numbers, I can use them for divisibility testing, in what you might call a process of elimination. Is 994 divisible by 23? No, because 989, a.k.a. 23×43, is.

   That's just a special case, though. What elimination is really good for is testing divisibility of a whole range of numbers all at once … you just find one that's divisible, then check off the rest in steps of m. That's not a new idea, by the way; the process I just described is none other than a single iteration in the sieve of Eratosthenes.

10. Ascending sequences. This method is another one that I haven't explained anywhere else. What it's good for is testing divisibility of a single number n by a sequence of numbers m … particularly, by the sequence of prime numbers. So, in other words, it's good for testing primality. The sequence doesn't have to be ascending, but there's no reason to pretend it's not.

    Here's how it works. Suppose we have the number n written out in terms of a quotient A and remainder B, as if we've divided by the prime p_i.

    n = Ap_i + B

    If the remainder is zero, we've found a factor, and are done; otherwise, we want to move to the next prime, p_i+1. To do that, we just replace p_i by p_i+1 in the equation, then balance that increase by a corresponding decrease in the second term, like so.

    n = Ap_i+1 + [B − A(p_i+1−p_i)]

    Finally, if the second term has become negative, we just shift a few p_i+1s from the first term. I won't bother writing an equation for that, I'll just let you see how it works in the following example.

    271 =	7	×	37	+	12
    	7		41		−16
    	6		41		25
    	6		43		13
    	6		47		−11
    	5		47		36
    	5		53		6

    In practice, it's not quite that easy … the quotient A always turns out to be inconveniently large. Still, I thought the idea was worth mentioning.

    The source of the idea is also worth mentioning. For some reason, I really dislike having to do long division by 29 and 31. So, before I realized there was a combined reduction rule based on 899, I had worked out a special way of handling those two. First I'd divide by 30—which is easy, you just ignore the last digit and divide by 3—and write the number as follows, …

    n = A×30 + B

    … then I'd use the relations below to check divisibility.

    n ≡ B + A mod 29
    n ≡ B − A mod 31

    Actually I checked A ± B … that works just as well, here.

So there you have it, a bunch of methods for divisibility testing. Some are more useful than others, but they're all at least a little bit useful; in fact I've used every one at least once.

There's one other method I wanted to mention, but I didn't want to include it in the list because it's speculative, and I've never used it. It occurred to me that, with practice, converting from one base to another is not necessarily an expensive operation. So, if you could find some base that complemented base 10 as far as which prime factors were easy to detect, it might be worthwhile to convert to that base and perform tests there. The remark about dividing by 30, above, leads in that direction … the reduction rules for 29 and 31 in base 30 are the same as the rules for 9 and 11 in base 10. The essay In Other Bases doesn't address this exact question, but it certainly contains a lot of relevant information.