Dr. Math FAQ || Classic Problems || Formulas || Search Dr. Math || Dr. Math Home
Divisibility Tests to 50 and Beyond
We know that to test for divisibility by (say) 15, we need only test for divisibility by 3 and 5. It follows that only the prime divisibility tests are required.
All the methods here work in the same recursive way. The number N1 is a multiple of prime P if (and only if) the smaller number N2 is also a multiple of P. These algorithms provide a way of reducing N1 to N2 (and N3, N4 etc.) until a multiple of P is recognised.
We wish to test the number 742 (N1) for divisibility by 7. We get to the smaller number (N2) by chopping off the units digit, multiplying it by 5 and adding it to the number of tens in the orginal number (N1):
Another example. Is 3647 divisible by 7?
I shall call this algorithm "Multiply by 5 and add".
The algorithm "Multiply by 2 and subtract" also works as a test for divisibility by 7:
These two algorithms form a "conjugate pair", one being "add" and the other being "subtract", as well as one being "multiply by m" and the other being "multiply by (p-m)", where p in this case is 7.
All this is leading up to the remaining divisibility tests. Each one uses the basic procedure of chopping off the units digit, multiplying it by m [or (p-m)] and then either adding to or subtracting from the truncated number.
Why These Methods Work
The simplest explanation, which is usually good enough for children, is that the procedure is just a fancy way of doing division by "chunking" - i.e., removing known multiples and just testing the remainder.
The Real Reason
The algorithm creates a smaller number that is a multiple of the prime being tested if and only if the original number was also a multiple. The explanation for the 7 test:
The General Procedure
The trick is simply to find the multiplying factor (m) for each number (p) to be tested. Playing with the algebra reveals that m is simply the first integer for which 10m-1 is divisible by p. The conjugate factor (p-m) is similarly the first integer for which 10(p-m)+1 is divisible by p. This gives the following table:
Lets use the table to test whether 3534 is divisible by 31. The algorithm is "Multiply by 3 and subtract":
Math Forum Home || Math Library || Quick Reference || Math Forum Search