In my previous post, I had come up with some simple divisibility rules for 16 and 32 (at least, simpler than simply checking divisibility by doing actual division on the last 4 or 5 digits of the number we need to check for divisibility). The rules involved splitting the last few digits of the number into chunks of various lengths, multiplying the chunks by different powers of 2, and then adding these parts up and checking the sum for divisibility by the powers of 2.

In that post, I also mentioned that I had not verified the correctness of these derived rules for divisibility because I was not a theoretical mathematician or number theorist. It turns out you don’t need to be either of those to come up with proofs of correctness (or incorrectness) of these rules, and also to derive new ones. The secret lies in modulo arithmetic, which I introduced in this earlier lesson during a discussion of how and why osculation works in deriving divisibility tests.

I also used those principles to derive a new divisibility rule for 7 that involved subtracting the number formed by the last 3 digits of the number from the rest of the number, and then checking to see if this is divisible by 7.

We can use the exact same principles to prove the divisibility rules for the powers of 2 that I published in the previous post, and also to derive new rules for these numbers.

First of all, let us get some basics out of the way. Any number with n+1 digits (say a) can be expressed as below:

10^{n}*d_{n} + 10^{n-1}*d_{n-1 }+ . . . + 10^{3}*d_{3} + 10^{2}*d_{2} + 10d_{1} + d_{0}

Now, we also know that divisibility of a number by 2^{m} implies that a mod 2^{m} = 0. Expanding out a, we can then say that:

(10^{n}*d_{n} + 10^{n-1}*d_{n-1 }+ . . . + 10^{3}*d_{3} + 10^{2}*d_{2} + 10d_{1} + d_{0} ) mod 2^{m} = 0

Knowing that 10^{m} and higher powers of 10 are multiples of 2^{m}, we can keep the modulo arithmetic intact by subtracting out these higher powers of 10. After the subtraction, all we are left with would be an (m-digit number) mod 2^{m} = 0. This is the basis for saying that we only need to concern ourselves with the last m digits of a number when checking divisibility by 2^{m}. Going forward, we will not even bother writing out the rest of the number to be checked for divisibility. We will only worry about the last m digits when proving or deriving divisibility rules for 2^{m}.

Let us also not worry about 2 to begin with. The divisibility rule for 2 is trivial, and needs no proving. Simply, since 10 and higher powers of 2 are multiples of 2 anyways, the entire modulo equation becomes simply x mod 2 = 0 implies divisibility by 2, where x is the last digit of the number.

Let us move on to 4. We know that 100 and higher powers of 10 are multiples of 4. So, for some number to be divisible by 4, we simply have to make sure that (10x + y) mod 4 = 0, where y is the last digit, and x is the last but one digit. In fact, this is the first divisibility rule for 4: the number formed by the last 2 digits has to be divisible by 4 for the entire number to be divisible by 4. But let us examine further.

(10x + y) mod 4 = 0 implies

(2x + y) mod 4 = 0, and also

(-2x + y) mod 4 = 0, and also

(2x – y) mod 4 = 0

The second line comes about because we subtracted 8x from (10x + y). We know this is valid because 8x is a multiple of 4. Similarly, we can get the third line by subtracting 12x from (10x + y). The fourth line is simply flipping the sign on the third line. Notice also that the second line is, in fact, the second rule for divisibility by 4. The third and fourth lines are in fact, brand-new rules for divisibility by 4 which I have not mentioned before.

Now, obviously, instead of subtracting 8x from (10x + y), I can choose to add 96x to (10x + y). After all 96x is a multiple of 4, so it is perfectly valid. But the resulting rule becomes more difficult to apply than the rule it was derived from (verifying that (106x + y) is divisible by 4 is a lot harder than verifying that (10x + y) is divisible by 4). Our goal should be to reduce the coefficients next to x and y as much as possible to make the arithmetic as easy as possible. 2 and –2 are the closest we are going to be able to get to zero from 10 by subtracting multiples of 4 from it, so we are better off stopping with the rules we have gotten above.

Also, (10x + y) mod 4 = 0 implies

(30x + 3y) mod 4 = 0 (I can multiply by 3 and the implication works in both directions because 3 and 4 are co-prime), which implies

(-2x + 3y) mod 4 = 0, and also

(2x – 3y) mod 4 = 0.

In the above cases, I subtracted 32x from (30x + 3y) since 32x is a multiple of 4. You can derive an infinite number of divisibility rules based on the rules of modulo arithmetic, and I think the above derivations show some of the possibilities. You are limited only by your imagination!

The rules above can be expressed in the form of a table as below. In this table, the column headings denote the digits in the various places. The coefficients by which these digits have to be multiplied are the elements of the table. The sum of these products is then checked for divisibility by 4 to verify the divisibility of the entire given number by 4. When the number under the “tens digit” column is 10, and the number under the “ones digit” is 1, this means that the 2-digit number formed by the two digits can be treated as a single chunk, multiplied by 1. Here are the 6 rules for divisibility by 4 in this notation.

**Divisibility Rules for 4:**

Rule Number | Tens Digit | Ones Digit |

1 | 10 | 1 |

2 | 2 | 1 |

3 | -2 | 1 |

4 | 2 | -1 |

5 | -2 | 3 |

6 | 2 | -3 |

To apply rule number 4, for instance, simply take twice the last but one digit and subtract the last digit from it. If the total obtained after this is divisible by 4, the entire number is divisible by 4.

Now that we know the basics of how to use modulo arithmetic to derive divisibility rules, applying the rules to 8 should be quite simple. First of all, 1000 and higher powers of 10 are multiples of 8, so we only have to deal with the last 3 digits of the number, which can be expressed as (100x + 10y + z). Without further ado, let us go about deriving some divisibility rules based on modulo arithmetic:

(100x + 10y + z) mod 8 = 0 implies

(4x + 10y + z) mod 8 = 0 (subtract 96x which is a multiple of 8), which implies

(4x + 2y + z) mod 8 = 0 (subtract 96x + 8y, which is a multiple of 8). Also,

(-4x + 10y + z) mod 8 = 0, which implies

(4x – 10y – z) mod 8 = 0. Also,

(-4x –2y + z) mod 8 = 0, which implies

(4x + 2y – z) mod 8 = 0. Also,

(300x + 30y + 3z) mod 8 = 0, which implies

(4x – 2y + 3z) mod 8 = 0, and also

(-4x –2y + 3z) mod 8 = 0, and

(4x + 2y – 3z) mod 8 = 0.

As you can see, the number of divisibility rules we can get is practically limitless. Here is a table with just a few of them:

**Divisibility rules for 8**:

Rule Number | 100s Digit | Tens Digit | Ones Digit |

1 | 100 | 10 | 1 |

2 | 4 | 10 | 1 |

3 | 4 | 2 | 1 |

4 | -4 | 10 | 1 |

5 | -4 | 2 | 1 |

6 | 4 | -2 | -1 |

7 | 4 | -6 | 1 |

8 | 4 | -2 | 3 |

9 | -4 | -2 | 3 |

10 | 4 | 2 | -3 |

If you continue this exercise for 16, 32, 64, etc., you will see that the generalized rule I came up with for using multi-digit chunks of a number to check for divisibility in this earlier post are wrong. Those rules were arrived at by intuition rather than rigorous mathematical analysis, and I am not surprised that some of them turned out to be wrong. Intuition is valuable in mathematics and science, but it should be backed by solid analysis and verification.

The number of divisibility rules goes up exponentially as the number for which divisibility is being checked goes up. So, I am not going to make any attempt to list them all in the tables below. I am just going to show you a representative few, including the rules I did come up with for 16 and 32 that are actually correct. So, here goes:

**Divisibility rules for 16**:

Rule Number | 1,000s Digit | 100s Digit | Tens Digit | Ones Digit |

1 | 1000 | 100 | 10 | 1 |

2 | 8 | 100 | 10 | 1 |

3 | 8 | 4 | 10 | 1 |

4 | 40 | 4 | 10 | 1 |

5 | 8 | 4 | -6 | 1 |

6 | -8 | 4 | -6 | 1 |

7 | 8 | -4 | 6 | -1 |

8 | -8 | 4 | 10 | 1 |

9 | 8 | -4 | -10 | -1 |

10 | 8 | 12 | -2 | 3 |

11 | -8 | -4 | -2 | 3 |

12 | 8 | 4 | 2 | -3 |

You may be able to recognize some of the rules from the previous post in the table above. For instance, rule 4 above is the second rule from the previous post. Rule 2 is the third rule from the previous post.

**Divisibility rules for 32**:

Rule Number | 10,000s Digit | 1,000s Digit | 100s Digit | Tens Digit | Ones Digit |

1 | 10000 | 1000 | 100 | 10 | 1 |

2 | 16 | 1000 | 100 | 10 | 1 |

3 | 16 | 8 | 100 | 10 | 1 |

4 | 16 | 8 | 4 | 10 | 1 |

5 | 16 | 40 | 4 | 10 | 1 |

6 | -16 | 8 | 4 | 10 | 1 |

7 | 16 | 8 | 4 | -22 | 1 |

8 | -16 | -24 | -28 | -22 | 1 |

9 | 16 | 24 | 28 | 22 | -1 |

10 | 80 | 8 | 100 | 10 | 1 |

11 | 16 | -8 | 12 | -2 | 3 |

12 | -16 | 8 | -12 | 2 | -3 |

The second rule from the previous post is rule number 5 in the table above. The third rule from the previous post is rule 10 above. And fourth rule from the previous post is rule number 2 in the table above.

I will leave you with a few divisibility rules for 64. You will notice that the general rules I postulated in my previous post for deriving divisibility rules for powers of 2 actually do not work with 64. That is one of the problems with trying to come up with or identify and extend patterns when you don't understand the underlying principles that result in the given pattern. I did not know what I was doing last week, and modulo arithmetic has enlightened me!

**Divisibility rules for 64**:

Rule Number | 100,000s Digit | 10,000s Digit | 1,000s Digit | 100s Digit | Tens Digit | Ones Digit |

1 | 100000 | 10000 | 1000 | 100 | 10 | 1 |

2 | 32 | 10000 | 1000 | 100 | 10 | 1 |

3 | 32 | 16 | 40 | 36 | 10 | 1 |

4 | 32 | 16 | -24 | -28 | 10 | 1 |

5 | -32 | 16 | -24 | -28 | 10 | 1 |

6 | 32 | -16 | 24 | 28 | -10 | -1 |

I will leave the derivation of divisibility rules for 128 and other higher powers of 2 to the readers (though I doubt you will encounter the need to check divisibility by such large numbers).

This was a lot of fun for me, and I hope you had fun reading this post. It is amazing how much you can discover in mathematics by using simple principles and applying them logically. The derivation of divisibility rules from modulo arithmetic is one such endeavor, where one of the most basic mathematical principles gives us such powerful results. I hope I have not made any arithmetic errors in this post. If I have, please do let me know. Good luck!

## No comments:

Post a Comment