Alternate Test Method

    Divisibility by powers of primes other than 2 and 5

Prime divisor 7

There is another way of testing for divisibility by powers of primes other than 2 and 5. We illustrate with the prime divisor 7.

This method uses the fact that 7 divides 2*10 + 1 = 21. Start with the numeral for the number you want to test. Chop off the last digit, double it, and subtract that from the rest of the number. Continue this until you get a one-digit number. The result is 7, 0, or -7, if and only if the original number is a multiple of 7.

Example:

        123471023473
    --> 12347102347 - 2*3 = 12347102341
    --> 1234710234 - 2*1 = 1234710232
    --> 123471023 - 2*2 = 123471019
    --> 12347101 - 2*9 = 12347083
    --> 1234708 - 2*3 = 1234702
    --> 123470 - 2*2 = 123466
    --> 12346 - 2*6 = 12334
    --> 1233 - 2*4 = 1225
    --> 122 - 2*5 = 112
    --> 11 - 2*2 = 7.

 
Here's another explanation for this rule, contributed by Dr. Mitteldorf:

When you separate the last digit from the rest of a number, it's like writing the number in the form 10x+y, where × is the number with the last digit lopped off and y is the last digit.

When you double the last digit and subtract from the number formed by the rest of the digits, you're computing x-2y. So the question becomes: why is it that whenever 10x+y is a multiple of 7, x-2y is also, and vice versa?

If x-2y is divisible by 7, then certainly 10*(x-2y) is divisible by 7. That's 10x-20y. And 21y is always divisible by 7. So the sum, 10x-20y+21y=10x+y, is also divisible by 7.

A little thought reveals that it also works the other way: If 10x+y is divisible by 7, and 21y is always divisible by 7, then 10x-20y must be divisible by 7. But this can be written 10(x-2y), and certainly the 10 isn't divisible by 7, so the x-2y must be.

- Doctor Mitteldorf, The Math Forum

---

Prime divisor 13

An analogous method works for 13, using the fact that 13 divides 4*10 - 1 = 39. Start with the numeral for the number you want to test. Chop off the last digit, double it, double it again, and add that to the rest of the number. Continue this until you get a number smaller than 40. The result is 13, 26, or 39 if and only if the original number is a multiple of 13.

Example:

        160518960524
    --> 16051896052 + 4*4 = 16051896068
    --> 1605189606 + 4*8 = 1605189638
    --> 160518963 + 4*8 = 160518995
    --> 16051899 + 4*5 = 16051919
    --> 1605191 + 4*9 = 1605227
    --> 160522 + 4*7 = 160550
    --> 16055 + 4*0 = 16055
    --> 1605 + 4*5 = 1625
    --> 162 + 4*5 = 182
    --> 18 + 4*2 = 26

---

Other prime powers up to 100 (multipliers at most 12)

Similar methods can be given for other prime powers, depending on finding a small multiple of them which ends in 1 or 9. We given the following table of prime powers up to 100 which have multipliers at most 12. This covers all of them with the exception of only 73, 83, and 97:

Prime Power      Chop size      Multiplier     + or -

     3               1               1           +
     7               1               2           -
     9               1               1           +
    11               1               1           -
    13               1               4           +
    17               1               5           -
    19               1               2           +
    23               1               7           +
    23               2               3           +
    27               1               8           -
    29               1               3           +
    31               1               3           -
    37               1              11           -
    37               3               1           +
    41               1               4           -
    43               2               3           -
    47               2               8           +
    49               1               5           +
    53               2               9           -
    59               1               6           +
    61               1               6           -
    67               2               2           -
    71               1               7           -
    79               1               8           +
    81               1               8           -
    89               1               9           +
    89               2               8           -

---

Other bases

If a numeral is written in a base R other than 10, similar rules can be devised for divisibility by prime powers. There are two main cases: when the prime divides R, and when it does not. When it does, looking at the last few digits of the numeral works. When it does not, all the digits of the numeral will come into play.

The first kinds of tests will depend on the prime power factorizations of R^k - 1 and R^k + 1 for positive integers k. The alternate kinds of tests described above can also be used, and the key here is to find small multiples of the divisor which end in 1, 01, 001, and so on, or which end in one or more digits (R-1).

There is another trick that you can always keep handy when checking for divisibility by anything. It's based on the techniques of modular arithmetic, which is a powerful tool, and lots of the other tests have their roots in modular arithmetic.

Let's say you have the number × = 3659867394557, and you want to know whether it's divisible by 7. You can take any number you see in × and replace it by the remainder you get when you divide that number by 7. For instance, the first two digits in x are 36. You can replace these by a 1, since 36/7 = 5 remainder 1. So now we only need to check the number 159867394557. We can do that wherever we want to. See that 45 near the end of the number? We can replace that with an 03, since 45/7 = 6 remainder 3. So now we have 159867390357. If we continue this process, it might look something like this:

    159867390357   (replace some of the big digits)
    152160320350   (start at the left and replace
     12160320350    the first few digits in each step)
      5160320350
       260320350
        50320350
         1320301

This isn't the most efficient method you've ever seen, but it's good to know that there are ways to simplify your numbers whenever you want to.