[NumTh Expository] Divisibility Tests for 7 and other digits

Introduction

     Let  n = ...ABCDEFG = ... + A´10⁶ + B´10⁵ + C´10⁴ + D´10³ + E´10² + F´10 + G. 

I invent the notation  ‘n ¸ d’  to mean  “n  is divisible by  d”  (as integers).  For a definition

n ¸ d   Û   d | n   Û   n = kd  for some integer  k

Many of you may have heard of the following divisibility tests:-

n ¸ 1   is always true   n ¸ 2   Û   the last digit  G ¸ 2   Û   the last digit  G Î {0, 2, 4, 6, 8}   n ¸ 3   Û   the sum of digits  ... A+B+C+D+E+F +G ¸ 3   n ¸ 4   Û   the last digits  FG ¸ 4   n ¸ 5   Û   the last digit  G ¸ 5   Û   the last digit  G Î {0, 5}   n ¸ 6   Û   n ¸ 2  and  n ¸ 3  (see above)   n ¸ 8   Û   the last digits  EFG ¸ 8   n ¸ 9   Û   the sum of digits  ... A+B+C+D+E+F+G ¸ 9 n ¸ 10   Û   the last digit  G = 0

What about divisibility by 7?

Modulo Arithmetic

     Divisibility tests are all based on modular arithmetic (a.k.a. clock arithmetic), as part of number theory.  This arithmetic was developed initally by a very clever mathematician

called Carl Friedrich Gauss.  The key idea is that numbers can be grouped into separate classes.  For example, when considering division by  3,  we can split the integers into three equivalence classes called residue classes

     [0] = { ..., -3, 0, 3, 6,   9, 12, ... }

     [1] = { ..., -2, 1, 4, 7, 10, 13, ... }

     [2] = { ..., -1, 2, 5, 8, 11, 14, ... }

The members of each class have the same remainder when divided by  3.  For example 

     10 ¸ 3 = 3r1,  7 ¸ 3 = 2r1,  4 ¸ 3 = 1r1  (all the remainders are equal to 1).

So  10, 7, 4, 1 ... etc are all members of the class  [1]  represented by  1.  Members of the same class are called congruent.  For example  10 º 4 (mod 3),  read as “10 is congruent to  4  modulo 3” and it means  10  and  4  have the same remainder when divided by  3.

a º b (mod m)   Û   (a – b) ¸ m   Û   a = b + km  for some integer  k

As you know,  “a ¸ m  gives a remainder of zero”  means  “a  is divisible by  m”.  Hence

a º 0 (mod m)   Û   a ¸ m

Congruency (for a given modulo m) is a type of equivalence relation.  We have these laws

Reflexivity:   For every integer a,  a º a Symmetry:    If  a º b,  then  b º a. Transitivity: If  a º b  and  b º c,  then  a º c.

These properties are similar to ‘=’.  We also have some very neat arithmetical laws.

Suppose  a º b (mod m)  and  c º d (mod m).  Then      a + c º b + d  (mod m)      a – c º b – d  (mod m)          ac º bd      (mod m)

For a given number  n = ...ABCDEFG,  we can write  n = 1000x + y   where  x = ...ABCD,  y = EFG.  With the above laws, modular arithmetic helps simplify calculations and provide powerful insights.  For example, in modulo 8,

         10 º 2,  100 º 10² º 2² º 4,  1000 º 10 ´ 10²  º 2 ´ 4 º 0.  Hence

         n = 1000x + y  º  0×x + y  º  y.

This explains the divisibility test by  8:  To see if a number is divisible by  8, we just need to look at the last  3  digits  y = EFG.

Test for divisibility by 7

     Using modulo 7,  10 º 3,  100 º 3² º 2,  1000 º 3 ´ 2 º 6 º -1.

     n = 1000x + y º  -1×x + y º  y – x.  Thus

     n ¸ 7   Û   n º y – x º 0   Û   x º y   Û    x – y ¸ 7.  We have the rule

n ¸ 7   Û   ...ABCD º EFG (mod 7)

This means that a number is divisible  7  if (and only if) after breaking off the last three digits, both resulting pieces have the same remainder when divided by  7.

Example 1

       For 12 516:  12 º 5  and  516 º 5 (mod 7).  So  12 516 ¸ 7.

Example 2

       For 654 321:  654 º 3  and  321 º 6 (mod 7).  So  654 321 not ¸ 7.

Example 3

       For 1 494 787:  787 º 3 º 1494 (mod 7).  So  1 494 787 ¸ 7.

       Alternatively, 1 494 – 787 = 707 ¸ 7.  So  1 494 787 ¸ 7.

Works like magic, doesn’t it?