It’s easy to tell if a given whole number is divisible by 2. Just check whether the last digit is even. There are also simple rules to determine whether a number is divisible by 3, 4, 5, 6, 8, 9, or 10. The exception is 7.
The known rules for testing for divisibility by 7 are amazingly cumbersome.
Here’s one such rule. To find out if a number is divisible by 7, double the last digit, then subtract it from the remaining digits of the number. If you get an answer divisible by 7, then the original number is divisible by 7. If you don’t know whether the new number is divisible by 7, you apply the rule again.
For example, to check whether 616 is divisible by 7, double the last digit (6 x 2 = 12), then subtract the answer from the remaining digits (61 – 12 = 49). Because 49 is divisible by 7, so is 616.
The method works quite well for small numbers. For larger numbers, the rule is sufficiently complicated that it takes nearly as much effort to check for divisibility as it would be to perform the division operation itself.
Over the years, people have come up with dozens of algorithms for divisibility by 7. The latest entry comes from Gustavo Gerald Toja Frachia of São Paulo University.
Here’s an example of how Toja’s ingenious method works.
- Consider the following multiple of 7:
6,049,344
- Separate the number into pairs of digits, starting from the right.
6 04 93 44
- Calculate the difference between each pair of digits and the nearest upper
or lower multiple of 7, beginning with the first pair at the right. For the
first pair, use the lower multiple, for the second use the upper multiple,
for the third use the lower multiple, and so on.
44 – 42 = 2; 98 – 93 = 5; 04 – 0 = 4; 7 – 6 = 1
- Write out the resulting digits in the order in which they were calculated.
2541
- Repeat the process on the digits 2541.
25 41
41 – 35 = 6;
28 – 25 = 3
63
- The final pair, 63, is a multiple
of 7. Hence, the original number must also be a multiple of 7.
Toja describes his method and explains why it works at http://www.divisibilitybyseven.mat.br/. He argues that his algorithm is remarkably fast and efficient for determining if large numbers are divisible by 7.
Alexander Bogolmolny recently extended Toja’s algorithm to divisibility by 11 and 13 (see http://www.cut-the-knot.org/blue/div7-11-13.shtml), and Toja added a way of determining the remainder when a number isn’t divisible by 7.
Interestingly, Toja’s method starts off in much the same way as an algorithm developed by L. Vosburgh Lyons, a New York neuropsychiatrist. This method was first disclosed by Martin Gardner in a 1962 Scientific American article.
Here’s the example that Gardner uses to demonstrate the Lyons test.
- From right to left, mark off the digits in pairs.
2 35 94 06 17 88 39
- For each pair, calculate its excess over a multiple of 7.
2 0 3 6 3 4 4
- Gather the excesses in groups of three, from the right, and add each of
the three columns separately.
3 4 4; 0 3 6; 2
3 + 0 = 3; 4 + 3 = 7; 4 + 6 + 2 = 12
- Reduce the three sums by calculating the excess of each over a multiple of 7.
3 0 5
- Record the excess of the first and second digits, taken together, over a multiple of 7 on the left. Record the excess of the second and third digits, taken together, over a multiple of 7 on the right.
2 5
- Subtract the left digit from the right digit. (If the right digit is smaller, add 7 before subtracting.) This final digit is the remainder when the original number is divided by 7. Thus, the original number is divisible by 7 if and only if this final digit is 0.
3
It still seems like a lot of work! There’s just something about 7 that brings in all sorts of complexities.
At a time when calculators and computers are ubiquitous, it’s not clear how useful it is to know algorithms for divisibility. Playing with numbers, however, has an enduring appeal, especially when it comes to mystical “7.”
