(by Polymath) This page is part of the Advanced High School Math Project.
I ran across this divisibility test for 7 in an old pre-algebra textbook. After figuring out how it works, I was able to generalize it. Since then, I've seen some other discussions of the generalization on the web, but it deserves to be better known, I think. The version for 11 is especially easy, but few people seem to know it.
The test for 7 goes like this (using 37499 as the number to be tested):
- Break off the last digit from the rest of the number to create two numbers: 3749 and 9
- Double the broken off last digit, and subtract that from the other new number: 3749-18=3731
- If the result is divisible by 7, then the original number is. Of course, you can test the result using the same procedure: the numbers are 373 and 1, so 373-2=371 .... and again: 37-2=35, which is clearly divisble by 7, so the original number was.
It works like this: the first of the two numbers created by breaking off the last digit (3749 in the example) is effectively the number in the tens column, so call it t, and call the units digit u. So the original number is 10t+u. The number created in step 2 is t-2u. So the claim is that 7|(t-2u) implies 7|(10t+u). I'm using the vertical bar to mean "divides".
Noting that multiplying a number by a non-multiple of 7 doesn't change divisibility by 7, nor does adding multiples of 7, we get:
7|10(t-2u) = 10t-20u iff
7|10t-20u+21u = 10t+u which was what we wanted.
The reason you need a 2 in the process is that you need to add a multiple of 7 with a final digit of 1 in the last step of the proof. Since that multiple is 21, you need to multiply by 2 (it's fairly obvious if you follow the 2 through the proof). The generalization uses the same pattern for other primes with multiples ending in 1 whose first digits are manageable:
For 7, the multiple is 21, so you multiply the final digit by 2 and subtract.
For 11, the multiple is 11, so you multiply the final digit by 1 and subtract (easy!!).
For 17, the multiple is 51, so you multiply the final digit by 5 and subtract.
You can also repeat the proof with addition and subtraction reversed, requiring multiples with a final digit of 9 (and using the next higher first digit to multiply--repeating the proof makes it clear why):
For 13, the multiple is 39, so you multiply the final digit by 4 and add.
For 19, the multiple is 19, so you multiply the final digit by 2 and add.
For 29, the multiple is 29, so you multiply the final digit by 3 and add.
Other tests are possible, but the arithmetic gets unwieldy. In these tests, with a paper and pencil to keep track of successive steps, the calculations are almost immediate, especially for 11:
testing 351,718 for divisibility by 19: