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

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.
It is not possible to use 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.
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.
Write where G is some unknown integer. From this, we get:10a + b = 7G b = 7G - 10a We want it to follow that a+mb is also a multiple of 7: where H is some other unknown integer.a + mb = 7H 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.
Write where G is some unknown integer. From this, we get:10a + b = 7G b = 7G - 10a We want it to follow that a-mb is also a multiple of 7: where H is some other unknown integer.a - mb = 7H 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.
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):
which is8524 -> 852 + 20 = 872 872 -> 87 + 10 = 97, *not*a multiple of 7, so neither is 8524. -
Test 9282 for divisibility by 7 using Test Type 2 (multiply
by 2 and subtract):
which9282 -> 928 - 4 = 924 924 -> 92 - 8 = 84, *is*a multiple of 7, so 9282 is too.
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.
Write where G is some unknown integer. From this, we get:10a + b = pG b = pG - 10a We want it to follow that a+mb is also a multiple of p: where H is some other unknown integer.a + mb = pH 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.
Write where G is some unknown integer. From this, we get:10a + b = pG b = pG - 10a We want it to follow that a-mb is also a multiple of p: where H is some other unknown integer.a - mb = pH 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 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 for some integer K. Thusa + mb = pK i.e., a+mb is still a multiple of p.a + mb - pb = p(K - b) 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! |

[**Privacy Policy**]
[**Terms of Use**]

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

© 1994- The Math Forum at NCTM. All rights reserved.

http://mathforum.org/