Home > Problem of the Week > Archive List > Detail

 << Prev 9/25/2011 Next >>

## The Case of the Special Multiplier to Test Divisibility

The divisibility tests for 2, 3, 4, 5, 6, 8, and 9 are both straight-forward and well-known. But, what about 7, 11, or 13, etc.?

Consider this test for determining divisibility by 7, using the test number 86415:

• Multiply the last digit 5 by the special number 2
• Subtract this product from the original test number, except its right-most digit has been truncated
• That is, 8641-(2)(5) = 8631
• Now, repeat this process, using 8631 as the new test number, etc.
• 863-(2)(1) = 861
• 86-(2)(1) = 84
• 8-(2(4) = 0
• Since 0 is divisible by 7, then so are 84, 861, 8631, and the original test number 86415
Question 1: Any idea why this algorithm works for the number 7? Any idea why 2 is the special multiplier?

Question 2: Generalize this algorithm for testing for divisibility by any positive integer N, provided N is relatively prime to 10.

Source: School Science and Mathematics, Nov. 1988, p. 629

Hint: The key is to discover the special multiplier that will make basically the same algorithm work for any N (relatively prime to 10).

So, play with some known numbers N such as 3 or 9 or 11 or 13...

Solution Commentary: Essence of solution posted by the SSMA: If the test number is x=10t+s, 0≤s≤9, then by the algorithm, N divides x iff N divides t-Ms.

Note, x=10t+s=10(t-Ms)+(10M+1)s implies that N, relatively prime to 10, will divide both x and t-Ms iff N also divides (10M+1)s. But, since s is a digit 0-9, we must choose M so that N divides 10M+1.

And, N, relatively prime to 10, N=10q+r where r=1, 3, 7, or 9. Also, note that

r=1 implies N=10q+1
r=3 implies 7N=10(7q+2)+1
r=7 implies 3N=10(3q+2)+1
r=9 implies 9N=10(9q+8)+1

Thus, for r = 1, 3, 7, 9, M can be chosen to be

q=(N-1)/10
7q+2=(7N-1)/10
3q+2=(3N-1)/10
9q+8=(9N-1)/10

The desired algorithm for computing M, given N relatively prime to 10, is thus

R:=N(mod 10)
Case R=1 : X:=1
R=3 : X:=7
R=7 : X:=3
R=9 : X:=9
M:=(X*N-1)/10

Now, this is all a mouthful. You need to first work through all of this to see why M=2 for the case of N=7. Then, test it out for other N such as 3, 9, 11, 13, and even 73!