In their exercises on reducing fractions, students are asked to notice that if a number is even it ends in an even digit and if it is divisible by 5 that it ends in a 0 or 5. Students are further asked to notice that if a number is divisible by 3, that the sum of the digits is divisible by 3. Students then often ask if there are similar criteria for telling if a number is divisible by other primes.
The most well known other case is 11.
Is 2574 divisible by 11?
Take the sum of every other digit in 2574
Next take the sum of the other digits.
Both sums come out the same and the number is divisible by 11.
What is the conclusion we can draw? One conclusion is that if the sum of the every other digits are the same, then the number is divisible by 11. However there are examples of numbers that are divisible by 11 where this is not the case
However if you take the sums of the every other digits
and the other sum is
The sums here are not the same, but their difference is 11. A criterion for determining if a number is divisible by 11 is if the difference in the sums of the every other digits is divisible by 11, then the number is divisible by 11.
Two questions arise at this point. One is why does this work and the other is are there any other primes for which there are similar criteria? Answering the second question would help to answer the first question.
Is there a criterion for determining whether a number is divisible by 7?
Is 111111 divisible by 7?
It is well known that 111111 is divisible by 7. It is easy to arrange a prime by prime reduction of the famous 142857/999999 to 1/7 so that the bottom will go through 111111. Here is a process for establishing the fact the number is divisible by 7.
Split off the last digit, double it and subtract the result from the remaining number.
If the remainder, 11109, is divisible by 7 then so will the original number. Is 11109 divisible by 7? To find out repeat the process
Repeat with 1092
Many people are familiar with the fact that 105 is divisible by 7, but let us continue anyway.
Since 0 = 0 x 7, the remainder is divisible by 7, and the result is established.
To see why this works, compare
These two computations contain almost the same information. The second one tells us that
Since 21 is a multiple of 7, any multiple of 21 is a multiple of 7, so the distributive law allows us to conclude that one of the other two numbers, 1050 and 1092, is divisible by 7 if and only if the other one is.
so by the result from the last activity, if 7 goes into 1050 it must go into either 105 or 10. Since 7 does not go into 10, it will go into 1050 if and only if it goes into 105.
This technique can be adapted for not only any prime besides 2 or 7 but any number which does not end in an even number or a 5. That will leave 1, 3, 7, and 9 as possible digits to be found in the one's place. Any such number has a multiple which ends in 1. For instance 13 x 7 = 91, so to tell if a number is divisible by 13 modify the above procedure by multiplying by 9 instead of by 2 when you split off the last digit.
This also explains why the method described above for 11 works. Here, you would be splitting off the last digit and multiplying it by 1. With the repeated subtractions, the signs would wind up alternating and we would eventually wind up with the difference of the every other sums.
Note that the sum of the digit process for 3 or for that matter 9 do not follow the format for the other primes. Why not? Can you develop another method for primes not equal to 2 or 5 which would reduce down to the sum of the digits method for 3 and 9?