It's nice to know that the ancient mathematicians of India were able to come up with a divisibility test for all divisors, but the method they published way back then can be somewhat simplified. Also, wouldn't it be nice to know *why* it works?

### Reduction to Prime Powers

To test for divisibility by any number that's the product of multiple different prime powers, you can just perform the divisibility rule for each prime power, and divisibility by their product will be established if all these succeed. So, for instance, a number is divisible by 6 if the divisibility checks for 2 and 3 both succeed.

So, we just need a way to generate rules for any prime power. To decide which method to use to generate a rule, we need only look at the remainder of the divisor when it is divided by 10, which is to say, its last digit.

### Powers of Two and Five

Since 2 and 5 are both 0 (mod 10), they have special rules. Namely, that a number is divisible by 2^k or 5^k if the last k digits, taken as a number, are divisible by 2^*k* or 5^*k*. This follows from the fact that 10^*k* is always divisible by both 2^*k* and 5^*k*.

### Prime Powers Ending in 1, 3, 7, and 9

All the rest of the residuals mod 10 (namely, 1, 3, 7, and 9) are relatively prime to 10, which means that we can divide the number we're testing by 10 without revoking its divisibility by whichever prime power we're interested in; if it was divisible by 17 before, it will still be divisible by 17 after we divide it by 10.

Which means we can just divide by 10 repeatedly until we get a number that's small enough we can check its divisibility at a glance! And dividing by ten is just as simple as chopping zeroes off the end of the number, so we don't even have to do any real math!

If only things were that easy, right? Unfortunately, the number we're testing might not be divisible by 10, which means no zero on the end to chop off. So how can we get a number that is divisible by 10? We can just subtract off the last digit, and we'll get a number that's divisible by 10! But...(of course there's a but...) subtracting an arbitrary number off the number WILL change the modulus; it might not be divisible by 17 after, even if it was before.

### The Osculator (Explained)

All is not lost, though! If we can figure out exactly how subtracting off that number changes the modulus and do something which undoes that change immediately while still leaving us with a number that is a multiple of 10, we can continue with our digit-chopping program with no problems.

So here's the plan: We'll multiply the digit we're subtracting off by some multiple of 10 so that the result will have a modulus exactly equal to the modulus we're subtracting off, and add this new number to the multiple of 10 we got from subtracting the digit off. The result will be a multiple of 10 also (as it is a sum of multiples of 10), yet it will be divisible by *n* if (and only if) the original number was divisible by *n*, because the changes in modulus in the subtraction and the addition exactly cancel each other.

For instance, we want to test the number 3094 for divisibility by 27. We need to make 3094 into a multiple of 10, so we subtract four from it, yielding 3090. This reduces its remainder mod 27 by four, so we multiply the four we removed by -80, yielding -320, which is equal to -12*27+4. In other words, it's congruent to 4 (mod 27), which means if we add it on, we'll be increasing the remainder mod 27 by four. This exactly offsets the subtraction by four we did in the previous step. The result of the sum is 2770, which is a multiple of 10, and is a multiple of 27 if and only if 3094 was. Now, we can divide it by 10 to get the number 277. We can tell at a glance that this number is not divisible by 27 (because it is 7 more than 27*10), so we are done; 3094 is not divisible by 27.

So, the only question that remains is this: How do we know which number to multiply by in that second step? How did I know to pick -8?

### Picking the Osculator

Let's go back and look at the residuals we don't yet know how to handle: 1,3,7, and 9. Since these numbers are relatively prime to 10, some multiple of each will yield a number which is 1 or -1 (mod 10). These are the easiest remainders to work with, and let us generate rules with ease. Why? Because, when considered mod any number that is 1 or -1 mod 10, multiplying by 10 is like multiplying by 1 or -1 respectively. Which is to say, in the former case, multiplying by 10 does not change its remainder, while in the latter case, it just swaps its sign.

As an example, let's let our modulus be 9. Since 10 is 1 (mod 9) multiplying by 10 is like multiplying by 1 (mod 9). For instance: 1 is 1 (mod 9). 10 is 1 (mod 9). 100 is 1 (mod 9) (=9*11+1). 1000 is 1 (mod 9) (=9*111+1).

Or as another example, let's let our modulus be 11. Since 10 is -1 (mod 11), multiplying by 10 is like multiplying by -1 (mod 11). For instance: 1 is 1 (mod 11). 10 is -1 (mod 11). 100 is 1 (mod 11) (=9*11+1). 1000 is -1 (mod 11) (=91*11-1).

So, remember what the second step was in the test-number-shortening process? Multiply the removed digit by a multiple of 10 that results in a number with the same exact same modulus as the digit removed. If we had a multiple of 10 that was known to be congruent to 1 (mod n), then we would just multiply by this multiple, knowing that it's the same as multiplying our digit by 1, and so will yield the correct modulus. If we had a multiple of 10 that was known to be congruent to -1 (mod n), we could just multiply by the opposite of this multiple, and know that it is again the same as multiplying our digit by 1, and that it will again yield the correct modulus.

For divisors ending with 1 or 9, the correct multiple of 10 is obvious: these numbers are directly adjacent to a multiple of 10, so we will use this one (or its opposite). E.g., for 29, we use 30, and for 61, we use -60 (negative, because 10 is -1 (mod 61)).

For divisors ending with 3 or 7, the correct multiple can be obtained by first multiplying the divisor by 3, thus yielding a number that ends in 9 or 1. Thus, for 13, we use 40 (because it is adjacent to 3*13=39), and for 17, we use -50 (because 3*17=51).

### Simplified Rules for 3, 9, and 11

Notice that the nearest multiple of ten for 3,9, and 11 is 10 itself. This means we don't even have to multiply the digit we chop off by anything (except -1, in the case of 11) when we shift it to add it to the remaining digits. As a result, we can just total all the digits at once to do the reduction in one big step (using an alternating sum in the case of 11 to account for the fact that you would be multiplying by -1 when shifting to the next digit). It's never going to be quite so nice for any other divisors.

### An Example

Now that the algorithm is described, let's do an example. Let's check whether 4913 is divisible by 17. As mentioned above, the fifth multiple of 10 is -1 (mod 17), so we will be multiplying by -5 in the second step.

First, we chop off the last digit, which means simultaneously subtracting 3 (which changes the modulus) and dividing by 10 (which maintains divisibility) to get 491. Next, we multiply the 3 by -5 to get -15, and add this to the remaining part of 491 (thus changing the modulus back). 491-15=476.

We repeat the process. Chop off the 6 leaving 47. 6*-5=-30. 47-30=17. 17 is obviously divisible by 17, so then 4913 must also be. (In fact, 4913=17^3.)

### Comparison to the Vedic Sutra

Upon reading the other writeup in this node, you'll note that this one differs in one major way. The ancient Hindu mathematicians computer the osculator by first multiplying a number ending in 1,3, or 7 by 9,3, or 7 respectively. Here, I replace the multiplication by 9 and 7 with multiplication by -1 and -3 respectively, which is possible because 9 is congruent to -1 (mod 10) and 7 is congruent to -3 (mod 10). This greatly increases the speed at which the calculations can be performed mentally, since the method in sutra could require you to multiply each digit by a number which is up to 9/10 of the divisor, quite a sizable multiplication for large divisors. Here, that factor is lowered to at most 3/10 of the divisor, so the numbers involved may be as much as 1/9 as large as they are in the sutra algorithm.

### A Note on Generalizing the Algorithm

This process cannot be used as-is to easily find out what the remainder is in the case that the test number is NOT divisible by the divisor. This is because dividing by 10 WILL change the modulus in this case. In order to find out what the remainder would be, one must keep track of how many reduction steps *k* one did before the remainder of the result was obvious, and then multiply that remainder, mod n, by 10^*k*. (Or, in the case of division by 7, multiplying by 3^*k* will do, as 10=3(mod 7).) However, one CAN use the digit sum method to determine a number's remainder mod 3 or 9 for reasons stated above. Likewise, one can use the alternating digit sum to find the remainder mod 11, provided you start by making the rightmost digit POSITIVE.