Drexel dragonThe Math ForumDonate to the Math Forum

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:

  1. 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.
  2. 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

[Privacy Policy] [Terms of Use]

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

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