Divisibility by 7

Some divisibility criteria are being taught in elementary school, some in middle school. The following is the summary of what a high schooler ought to know.

1. A number is divisible by 2, 5, or 10 if its last digit is divisible by, correspondingly, 2, 5, or 10.
2. A number is divisible by 3, or 9 if the total of its digits is divisible by, correspondingly, 3, or 9.
3. A number is divisible by 4 if its last 2 digits are divisible by 4.
4. A number is divisible by 8 if its last 3 digits are divisible by 8.
   

One might wonder when is the number divisible by 7 ? To answer this question it is useful to remember some properties of modular arithmetic. These are

1. (a*b) mod n = (a mod n)*(b mod n) mod n
2. (a+b) mod n = (a mod n) + (b mod n) mod n

Thus for n = d[0] + d[1]*10^1 + d[2]*10^2 + ... + d[k]*10^k,

n mod 7 = sum( d[k] (10^k mod 7), over k )

Quick check in Mathematica shows that 10^k mod 7 is periodic with period 6:

In[30]:= Table[Mod[PowerMod[10, k, 7], 7, -3], {k, 0, 12}]

Out[30]= {1, 3, 2, -1, -3, -2, 1, 3, 2, -1, -3, -2, 1}

This gives the divisibility by 7 test. The number is divisible by 7 if the cyclic sum of its digits (starting with rightmost one) with {1,3,2,-1,-3,-2} is divisible by 7. The following is a Mathematica code to compute this cyclic sum:

DivisibilityBySevenTest[n_Integer] :=
With[{dig = Mod[Reverse[IntegerDigits[n]],7]},
   dig.PadRight[{},Length[dig], {1,3,2,-1,-3,-2}]
]

Consider an easy example. Let n = 28. Since 8 mod 7 = 1, we have (8 mod 7)*1+2*3 = 7, and, of course, 28 = 7*4.

In[47]:= DivisibilityBySevenTest[28]

Out[47]= 7

Now take n=2009. We do (9 mod 7)*1 + 0*3+0*2+2*(-1) = 2-2 = 0.

In[48]:= DivisibilityBySevenTest[2009]

Out[48]= 0

Indeed:

In[46]:= 2009/7

Out[46]= 287

When manually applying the divisibility test for large numbers, it might be easier to use the fact that 1000^k mod 7 is (-1)^(k-1). Thus, we might first form an alternating sum of triples of digits, and test the result afterwards. For example, let n = 123,456,789. It is divisible by 7 if 789 - 456+123 = 333+123 = 456 is divisible by 7. To check this, we compute 6*1+5*3+4*2 = 6+15+8=29 = 1 mod 7. Thus the number n is not divisible by 7. Indeed,

In[50]:= QuotientRemainder[123456789, 7]

Out[50]= {17636684, 1}

Applying the divisibility by 7 directly we get

In[53]:= DivisibilityBySevenTest[123456789]

Out[53]= -13