## Saturday, November 12, 2011

### Divisibility Rules For Powers Of 2 Redux

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:

10n*dn + 10n-1*dn-1 + . . . + 103*d3 + 102*d2 + 10d1 + d0

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

(10n*dn + 10n-1*dn-1 + . . . + 103*d3 + 102*d2 + 10d1 + d0 ) mod 2m = 0

Knowing that 10m and higher powers of 10 are multiples of 2m, 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 2m = 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 2m. 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 2m.

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!

## Content From TheFreeDictionary.com

In the News

Article of the Day

This Day in History

Today's Birthday

Quote of the Day

Word of the Day

Match Up
 Match each word in the left column with its synonym on the right. When finished, click Answer to see the results. Good luck!

Hangman

Spelling Bee
difficulty level:
score: -