Return to my Mathematics pages
Go to my home page
© Copyright 1999, Jim Loy
How do you tell if a number is divisible by 2? If it is an even number (ends in 0, 2, 4, 6, or 8) it is divisible by 2. Another way to tell is to divide by 2, and if there is no remainder, then it is divisible by 2. This test depends heavily upon the base we are using; we use base-10. If the base is 2, then a number is divisible by 2 if it ends in 0 (1101010 is divisible by 2 (10 in base 2)). If the base is odd, then divisibility by 2 is more difficult to determine.
Here are divisibility tests for the first few integers (2 through 11):
There are some interesting things in this list. Some of the tests deal with just a few of the digits of a number. If we want to determine if a 30-digit number is divisible by 4, we can ignore the first 28 digits. The last two digits are all that matter. Other tests deal with the entire number. These involve numbers which are relatively prime to 10. All of the above tests are relatively easy to prove. This whole subject can be best examined using Modular Arithmetic. But, in this article, I will not bother with that.
Divisibility by 3 involves summing up all of the digits, and seeing if the sum is divisible by 3. This process can be repeated. Let's say we have a hundred digit number, and we sum up the digits, and we get a three digit number. We can perform the same test on this three digit number. Also, we could just cross out all of the 3's, 6's, and 9's in our long number, and then sum up the rest of the digits. That can be justified using modular arithmetic, by the way. We can do other things, like substitute 2's for 5's. Why not just divide the whole number by 3, and see if there is a remainder? Besides the fact that doing it in other ways is an interesting puzzle, my calculator will not let me divide a huge number by 3. And I don't want to do it by hand, either.
Divisibility by 11:
Divisibility by 11 is the most interesting of the above tests (7 will be studied below). We do two sums (the odd numbered digits and the even numbered digits), subtract one sum from the other, and see if this is divisible by 11. By the way, if we end up with zero, then that is divisible by 11. We can repeat that process, just as we did with 3. Let's look at an example:
34871903
3+8+1+0=12
4+7+9+3=23
23-12=11
Is divisible by 11
We can, of course, do the summing in different orders. In fact we can just go from left to right adding and subtracting alternate digits: 3-4+8-7+1-9+0-3=-11 (divisible by 11).
Divisibility by 7:
Now we will study divisibility by 7. One book on speed arithmetic says that these tests are just too complicated, and you should just divide by 7. I agree to some extent, but my calculator still will not let me enter really large numbers.
One interesting way (found in some books) is to take the two left-most digits, multiply the left digit by 3 and add it to the second digit. Replace these two digits with the result. Then we can keep repeating, always dealing with only the two left-most digits, until we end up with a small number which is either divisible by 7 or not. Pretend we have a two digit number, 10x+y. We multiply the left digit by 3 and add the second digit: 3x+y. All we did was just subtract 7x. If 3x+y is divisible by 7, then so is 10x+y. This works at the left end of a long number, too. The two left-most digits are 10x+y times some power of 10. Multiplying the left digit by 3 and adding the second digit gives us 3x+y times the same power of 10. And we subtracted off 7 times the same power of 10. Again, divisibility by 7 was not altered.
4712954379
1912954379
1212954379
512954379
162954379
92954379
29954379
15954379
8954379
3354379
1254379
554379
204379
64379
22379
8379
2779
1379
679
259
119
49
49 is divisible by 7. We could have stopped the process once we got a number that was small enough for my calculator, and divided the current number by 7. Since 49 is divisible by 7, every number above it is also divisible by 7.
Modular arithmetic gives us the following method. Start at the right digit, and go left. 1st digit + 3 times the 2nd digit + 2 times the 3rd digit - the 4th digit - 3 times the 5th digit - 2 times the 6th digit. And then we repeat the sequence, + the 7th digit + 3 times the 8th digit, etc. If the whole "sum" is divisible by 7, then the original number is divisible by 7.
4712954379
9+3(7)+2(3)-4-3(5)-2(9)+2+3(1)+2(7)-4=14
14 is divisible by 7. You can see that this is a much faster method. With really huge numbers, you might need to repeat the above steps.
I use a different method. I separate the huge number into 6-digit numbers (4712 954379), add them together (4712+954379=959091). I use my calculator to divide this by 7, and there is no remainder (959091/7=137013 with no remainder), so the original number is divisible by 7. With really huge numbers, I may have to repeat these steps. This method works for divisibility by 13, by the way. The above number is not divisible by 13. Why do we separate the number into 6-digit numbers? Well again, modular arithmetic produces that information. For divisibility by 37, we separate the long number into 3-digit numbers.
Addendum:
I received email from Jordan Baker, describing another test for divisibility by 7: "Take the last digit off, double it, and subtract it from the rest of the numbers. If the result is divisible by 7, so was the original number." And that can be repeated, of course. He gave this example: "Take a number like 408254, which is divisible by 7. Take the 4 off the end, and double it: 8. 40825 - 8=40817." Then he repeated the process.
Here is my explanation of why this works:
A many digit number is 10x+y (for example, 3176 is 317(10)+6). 10x+y is divisible by 7 if and only if 20x+2y is divisible by 7 (that is twice the original number, doubling it does not affect its divisibility by 7, as 2 and 7 are relatively prime). We can subtract 21x from 20x+2y without affecting its divisibility by 7 (21x is divisible by 7). That gives 2y-x (which is usually a negative number, by the way). So, 10x+1 is divisible by 7 if and only if 2y-x is divisible by 7. The method that Mr. Baker showed me was x-2y, which is -(2y-x). So 10x+1 is divisible by 7 if and only if x-2y is divisible by 7.
I thought that I had seen that method before. Here is actually what I had seen before, from The Dictionary of Curious and Interesting Numbers, by David Wells: Multiply the right-most digit by 5 and add to the rest of the numbers. If this sum is divisible by 7, then the original number is divisible by 7. And that too can be repeated. This is a slow method. It is roughly as fast as the above methods (3x+y and x-2y) until near the end, and then it can take 5 or 6 extra steps. Also, if you end up with 49, you get no further, as the next number is also 49. Otherwise, you can keep repeating the process until you get a one digit number (7). Why does it work?
Our original number is 10x+y. We can multiply that by 5 without affecting its divisibility by 7: 50x+5y. We can subtract off 49x (which is divisible by 7) without affecting its divisibility by 7: x+5y. And x+5y is the method described.
Note: For the time being, I will not deal with divisibility by larger numbers.