## Tuesday, July 10, 2012

### Divisibility by 7

There are lots of different divisibility tests out there -- here's a review of techniques for checking if a number N is divisible by seven:

1. Divide it. If you have a calculator, type N / 7 and see what comes up. If you get a clean integer, then N is divisible. If you don't have a calculator, then use long division or another approach and see what you get. Of course, this isn't really a "divisibility test" in the usual sense, but with a calculator its usually the fastest technique.

2. Arrange it. Grab N objects and line them up in rows of 7. If there is no objects left over at the end, then N is divisible. Again, not the most practical, but it would be fun. Even better, grab N volunteers and have them arrange themselves on a football field in rows of 7. Again, the key would be to have no incomplete rows when you are done.

3. Write the number in base 7. If the number ends in a 0, then N is divisible by seven. This method might be less practical than #2.

4. Recognize it. Some numbers, especially the 2-digit numbers, you might just recognize as being divisible by 7. It is helpful to recognize them all, for some of the later tests, but the only two-digit ones you might not already have memorized are 84, 91, and 98. I'll include in this category a couple of others you probably didn't already know:
Any 6 digit number that repeats in groups of three is divisible by 7. For example, 326,326 and 199,199 are multiples of 7, as is 36,036.  That's because each of these numbers is a multiple of 1001, which is divisible by 7.

5. Subtract ones from the rest twice:  Here I'll discuss our first "legitimate" divisibility test, which takes as many steps as the number of digits in N. Chop off the last digit of N and subtract it twice from the rest of N. Then do this again, and again, until your number is small enough to recognize as a multiple of 7. Here's an example:
Is 765898 divisible by 7?
Subtract 8 from 76589 twice: 76581, 76573
Subtract 3 from 7657 twice: 7654, 7651
Subtract 1 from 765 twice: 764 763
Subtract 3 from 76 twice: 73, 70
Recognize that 70 is a multiple of 7 and therefore 765898 must have been also.

6. The technique can be helped if you take advantage of another property. At any point in the process if a digit is too big or two small, you can add or subtract 7 from it without affecting the test. This can help reduce the number of times you have to borrow in the process -- which I made mistakes on three times in just the four step example above. Also, any 7's at the beginning or end of a number can be chopped off without affecting the test.  Here's another look at it, with a few short cuts.
Is 765898 divisible by 7?  Chop off the first 7, and reduce the ones digit by 7.
Is 65891 divisible by 7?
Subtract 1 from 6589 twice: 6588 6587
Chop the 7, is 658 divisible by 7?
Is 651 divisible by 7?  Subtract the 1 twice from 65.  64, 63. Bingo! 63 is 7*9.

7. For 4, 5, or 6 digit numbers, subtract the chunks of three digits and test their difference: Using the same example, 765898 is divisible by 7 because 898 - 765 is 133 and 133 is divisible by 7.

8. Add or subtract 7's (or 70's, or 700's, etc.) till you recognize a multiple. In the example above, I noticed that 133 is 7 short of 140, a known multiple of 7.  Earlier, I noticed that 658 was 28 more than 630, and so I recognized that 658 would have been a multiple of 7.

9. For larger numbers (more than 6 digits) alternately subtract and add chunks of three digits and apply a test:
Is 369,339,554,237,199 divisible by 7? 369-339+554-237+199 = 546.  Since 546 is 14 short of 560, it is divisible by 7. This number was to big to use my calculator for, but I could still figure out if it's divisible by 7, in just about as much time as it takes for me to type it in, as shown below.

 Three Tests for Divisibility by Seven: 1. Direct test (number was too big to use) 2. Reduce by alternating sum/differences 3. Fractional Part Test.
10. Try modular arithmetic. Some calculators can find the remainder of an answer, even though the number itself is beyond the size the calculator can handle. For TI80's, this can be exploited using fpart() located in the math menu. Include this in your calculation and it will only handle the remainder. If you find that the fpart of a division is zero, than the number divided evenly. If it something between 0 and 1, you can multiply it by 7 and that whole number is the remainder.  It worked with remarkably big numbers on my calculator -- I could work with numbers with 100 digits, but it gave me an over flow at 120 digits -- so somewhere in there is the calculator's limit. I suppose if you have a bigger number than that, you could either reduce it down using #8 above, or just wolfram it.

Your turn: Assignment: Prove why some of the techniques from #4-9 work. Alternatively, find a 8 digit number that is divisible by 7, and one that isn't, and demonstrate several of techniques. Go!