Ask Dr. Math: FAQ

Dr. Math FAQ || Classic Problems || Formulas || Search Dr. Math || Dr. Math Home

Divisibility Tests to 50 and Beyond by Stephen D. T. Froggatt Oaks Park High School, Ilford, Essex, UK Back to Divisibility Rules 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. Some examples 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): 742 -> 74 + (2 x 5) = 84, which is clearly a multiple of 7 Therefore 742 is also a multiple of 7. Another example. Is 3647 divisible by 7? 3647 -> 364 + (7 x 5) = 399 399 -> 39 + (9 x 5) = 84, which is a multiple of 7. Therefore 3647 is also a multiple of 7 (and incidentally, so is 399). 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: 3647 -> 364 - (7 x 2) = 350 350 -> 35 - (0 x 2) = 35, which is a multiple of 7 Therefore 3647 is also a multiple of 7 (and incidentally, so is 350). 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 original number (N1) can be written in the form 10a + b. For example, if N1 is 742 then a = 74 and b = 2. Let's assume that 10a + b is a multiple of 7. Then 10a + b = 7k for some integer value of k. Then b = 7k - 10a. And a + 5b = a + 35k - 50a = 35k - 49a = 7 (5k - 7a) So this is clearly a multiple of 7 as well. 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: Divisibility Test (p) Factor (m) Conjugate Factor (p-m) Best Algorithm 7 5 2 x5 and add 11 10 1 x10 and add 13 4 9 x4 and add 17 12 5 x5 and subtract 19 2 17 x2 and add 23 7 16 x7 and add 29 3 26 x3 and add 31 28 3 x3 and subtract 37 26 11 x11 and subtract 41 37 4 x4 and subtract 43 13 30 (either) 47 33 14 (either) 53 16 37 (either) Let’s use the table to test whether 3534 is divisible by 31. The algorithm is "Multiply by 3 and subtract": 3534 -> 353 - (4 x 3) = 341 341 -> 34 - (1 x 3) = 31 which is a multiple of 31 Therefore 3534 is divisible by 31.

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. Math ®
© 1994-2013 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.