### Ask Dr. Math:FAQ

Divisibility Tests to 50 and Beyond

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

 Back to Divisibility Tests to 50 and Beyond Constructing The Divisibility Test For 7 Using Simple Algebra We wish to devise a test that transforms one number into a smaller one with the result that the larger number is divisible by 7 if and only if the smaller number is too. A suitably efficient test would reduce the number of digits by 1 at each stage. Notation It is not possible to use the notation abcde to represent a five-digit number with digits a, b, c, d, and e in that order, since abcde refers to the product of those five variables. We must use instead the notation ```10000a + 1000b + 100c + 10d + e. ``` Actually we can do better than that. Since we are only interested in the tens and units columns we can call our number 10a + b. For example, 74629 has a = 7462 and b = 9. Developing the Algebra The algebra is simply a matter of using this notation to describe the way we want the test to work, and then simplifying it to make it more user-friendly. In words, what we want is to chop off the units digit, multiply it by something suitable, then either add it to or subtract it from our truncated number. In the language of algebra, this is: ```Starting number: 10a + b Truncated number: a Smaller number: a + mb or a - mb ``` If 10a+b is a multiple of 7, we want it to follow that a+mb (or a-mb) is too. In algebra, if something is a multiple of 7, we can write that it is equal to 7 times some whole number. Type 1: a + mb Write ```10a + b = 7G ``` where G is some unknown integer. From this, we get: ```b = 7G - 10a ``` We want it to follow that a+mb is also a multiple of 7: ```a + mb = 7H ``` where H is some other unknown integer. Now, ```a + mb = a + m(7G - 10a) = a + 7mG - 10ma = (1 - 10m)a + 7mG ``` This is only a multiple of 7 if (1-10m) is, since 7 clearly divides 7mG. It is easier to follow if we multiply by -1, i.e., by requiring (10m-1) to be a multiple of 7. So, what value of m makes (10m-1) divisible by 7? Well, 49 is the first multiple of 7 ending in 9, so that gives us m = 5. Type 2: a - mb Write ```10a + b = 7G ``` where G is some unknown integer. From this, we get: ```b = 7G - 10a ``` We want it to follow that a-mb is also a multiple of 7: ```a - mb = 7H ``` where H is some other unknown integer. Now, ```a - mb = a - m(7G - 10a) = a - 7mG + 10ma = (10m + 1)a - 7mG ``` This is only a multiple of 7 if (10m+1) is, since 7 clearly divides 7mG. So, what value of m makes (10m+1) divisible by 7? Well, 21 is the first multiple of 7 ending in 1, so that gives us m = 2. The Divisibility Test We now have the results we need - two in fact, since there are two different ways of carrying out the test, one with addition and the other with subtraction: Type 1 gives us the result that if 10a + b is a multiple of 7, then so too is a + 5b. Type 2 gives us the result that if 10a + b is a multiple of 7, then so too is a - 2b. Examples: Test 8524 for divisibility by 7 using Test Type 1 (multiply by 5 and add): ```8524 -> 852 + 20 = 872 872 -> 87 + 10 = 97, ``` which is not a multiple of 7, so neither is 8524. Test 9282 for divisibility by 7 using Test Type 2 (multiply by 2 and subtract): ```9282 -> 928 - 4 = 924 924 -> 92 - 8 = 84, ``` which is a multiple of 7, so 9282 is too. Generalising For Primes Other Than 7 We just run through the algebra again, using p as the prime number for which we wish to create a divisibility test. ```Starting number: 10a + b Truncated number: a Smaller number: a + mb or a - mb ``` As before, if 10a + b is a multiple of p, we want it to follow that a+mb (or a-mb) is too. If something is a multiple of p, we can write that it is equal to p times some whole number. Type 1: a + mb Write ```10a + b = pG ``` where G is some unknown integer. From this, we get: ```b = pG - 10a ``` We want it to follow that a+mb is also a multiple of p: ```a + mb = pH ``` where H is some other unknown integer. Now, ```a + mb = a + m(pG - 10a) = a + pmG - 10ma = (1 - 10m)a + pmG ``` This is only a multiple of p if (1-10m) is, since p clearly divides pmG. It is easier to follow if we multiply by -1, i.e., by requiring (10m-1) to be a multiple of p. So, what value of m makes (10m-1) divisible by p? Just substitute a few values of p and see what you get. For example, for p = 13, we have 39 as a multiple of p and so for p = 13, m = 4. Type 2: a - mb Write ```10a + b = pG ``` where G is some unknown integer. From this, we get: ```b = pG - 10a ``` We want it to follow that a-mb is also a multiple of p: ```a - mb = pH ``` where H is some other unknown integer. Now, ```a - mb = a - m(pG - 10a) = a - pmG + 10ma = (10m + 1)a - pmG ``` This is only a multiple of p if (10m+1) is, since p clearly divides pmG. So, what value of m makes (10m+1) divisible by p? Just substitute a few values of p and see what you get. For example, for p = 13, we have 91 as a multiple of p and so for p = 13, m = 9. The Link Between Type 1 and Type 2 The two values of m thus obtained always add up to p. Why is this? A final bit of algebra will show us the reason. Let a+mb be a multiple of p. Then ```a + mb = pK ``` for some integer K. Thus ```a + mb - pb = p(K - b) ``` i.e., a+mb is still a multiple of p. In other words, a-(p-m)b is a multiple of p as well. Call this the "conjugate" test. The two tests are then a+mb and a-(p-m)b. We simply choose whichever seems to be the easiest to use in practice. Of course there is no theoretical upper limit to the tests that can be created in this way, but after about 50, the question of practical value becomes more important!

Back to Divisibility Tests to 50 and Beyond

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

© 2015 Drexel University. All Rights Reserved. http://mathforum.org/pows/