Divisibility Algorithm

Date: 11/26/2001 at 19:02:40
From: Matt Trzebiatowski
Subject: Multiples of seven

Is there a trick for figuring out multiples of seven?

Date: 11/27/2001 at 12:59:23
From: Doctor Greenie
Subject: Re: Multiples of seven

Hi, Matt -

Here is a method you can use to find out if a number is divisible 
by 7:

   Take the last digit, double it, and subtract it from the rest
   of the number; if the answer is divisible by 7 (including 0),
   then the number is also.

I found this rule in the Dr. Math FAQ, by following the link to the 
section titled "Divisibility Rules."  You can often find answers to 
your questions by taking a bit of time to search the Dr. Math FAQs or 
the Dr. Math archives.

This method is an algorithm rather than a rule; it typically needs to 
be applied several times to reach a conclusion. Here is an example of 
the use of the rule to show that 316463 is divisible by 7:

   316463; last digit 3 doubled is 6; 31646-6 = 31640
    31640; last digit 0 doubled is 0; 3164-0 = 3164

          (note I followed the algorithm exactly here; I could have
           skipped this step by simply dropping the final 0, because
           if 31640 is divisible by 7, then 3164 must be also)

     3164; last digit 4 doubled is 8; 316-8 = 308
      308; last digit 8 doubled is 16; 30-16 = 14

At this point, we know 14 is divisible by 7, so the original number 
316463 is also divisible by 7.

This algorithm is somewhat difficult to remember; I use a different 
algorithm which gets me to an answer almost as quickly and which can 
be used to test for divisibility by ANY number.

With the algorithm I use, I simply look at the rightmost nonzero 
digits and add or subtract multiples of the number I am dividing by to 
make the last digits 0.

Here is my algorithm, applied to the same example as above, to show 
that 316463 is divisible by 7:

   316463; rightmost nonzero digit 3; add 7 to get 316470
   316470; rightmost nonzero digit 7; subtract 7 to get 316400
   316400; rightmost nonzero digit 4; subtract 14 (2*7) to get 315000
   315000; rightmost nonzero digit 5; add 35 (5*7) to get 350000
   350000...

At this point I can see the number is divisible by 7, so the original 
number 316463 is also divisible by 7.

The algorithm can be used to show divisibility by any number, although 
it becomes impractical for large divisors. Here is the algorithm used 
to show that 6678204 is a multiple of 13:

 6678204; rightmost nonzero digit 4; add 26 (2*13) to get 6678230
 6678230; rightmost nonzero digit 3; subtract 13 to get 6678100
 6678100; rightmost nonzero digit 1; add 39 (3*13) to get 6682000
 6682000; rightmost nonzero digit 2; subtract 52 (4*13) to get 6630000
 6630000; rightmost nonzero digit 3; subtract 13 to get 6500000
 6500000...

At this point I can see that the number is divisible by 13, so the 
original number 6678204 is also divisible by 13.

I hope this helps.  Write back if you have further questions on this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/