Explaining the Divisibility Rule for 7

Date: 02/26/2003 at 10:40:57
From: Abhay Dang
Subject: Proving divisibility rule for 7

I found in the Dr. Math FAQ the rule for divisibility of a number 
by 7. 

   Why do these 'rules' work?
   http://mathforum.org/k12/mathtips/division.tips.html 

Please explain (prove) why the following rules work.

Rule 1) Divide the number into groups of 3 starting from the right and 
give these groups alternating +/- signs. Apply the rule again if 
necessary until you get a three-digit number. The original number is 
divisible by 7 if this sum is. Eg. for 123456789 => 789 - 456 + 123 

Rule 2) To know if a number is a multiple of seven or not, we can use 
also 3 coefficients (1, 2, 3). We multiply the first number starting
from the ones place by 1, then the second from the right by 3, the
third by 2, the fourth by -1, the fifth by -3, the sixth by -2, the
seventh by 1, and so forth.

Example: 348967129356876. 
6 + 21 + 16 - 6 - 15 - 6 + 9 + 6 + 2 - 7 - 18 - 18 + 8 + 12 + 6 = 16 
means the number is not multiple of seven.

So the pattern is as follows: for a number onmlkjihgfedcba, calculate
a + 3b + 2c - d - 3e - 2f + g + 3h + 2i - j - 3k - 2l + m + 3n + 2o.

Example:  348967129356874.

Below each digit let me write its respective figure.

3  4  8  9  6  7  1  2  9  3  5  6  8  7  6 
2  3  1 -2 -3 -1  2  3  1 -2 -3 -1  2  3  1

(3*2) + (4*3) + (8*1) + (9*-2) + (6*-3) + (7*-1) + 
(1*2) + (2*3) + (9*1) + (3*-2) + (5*-3) + (6*-1) + 
(8*2) + (7*3) + (6*1) =  16 -- not a multiple of seven.

Kindly explain and prove why these rules work.

Best regards
Abhay Dang

Date: 03/04/2003 at 13:02:51
From: Doctor Peterson
Subject: Re: Proving divisibility rule for 7

Hi, Abhay.

The key here is that

    1000 = 7*143 - 1

Consequently,

    1000^2 = (7*143 - 1)^2 = 7^2*143^2 - 2*7*143 + 1

If you think about how higher powers work, you will see that

    1000^1 = 7A - 1
    1000^2 = 7B + 1
    1000^3 = 7C - 1

and so on (where A, B, C, and so on are some whole numbers).

This can be better expressed in terms of modular arithmetic, if you 
are familiar at all with that; 1000^n is congruent (mod 7) to -1 when 
n is odd, and to +1 when n is even.

So looking at the number "abc,def,ghi", and calling the numbers "abc," 
"def," and "ghi" X, Y, and Z respectively, we can write it as

    1000^2 X + 1000 Y + Z

which is equal to

    (7B+1)X + (7A+1)Y + Z = 7(BX + AY) + (X - Y + Z)

Do you see that this will be divisible by 7 if and only if X-Y+Z is 
divisible by 7? The same pattern continues for additional digits.

>Rule 2) 

This is very similar, using the facts that

       1 =         1
      10 = 7*1   + 3
     100 = 7*14  + 2
    1000 = 7*143 - 1

Can you fill in the rest of the reasoning?

If you have any further questions, feel free to write back.

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

Date: 03/05/2003 at 10:01:53
From: Abhay Dang
Subject: Thank you (Proving divisibility rule for 7)

Thanks a lot. You've been of great help !