The Case of the Special Multiplier to Test Divisibility
The divisibility tests for 2, 3, 4, 5, 6, 8, and 9 are both straightforward and wellknown. 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 rightmost 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 tMs.
Note, x=10t+s=10(tMs)+(10M+1)s implies that N, relatively prime to 10, will divide both x and tMs iff N also divides (10M+1)s. But, since s is a digit 09, 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=(N1)/10
7q+2=(7N1)/10
3q+2=(3N1)/10
9q+8=(9N1)/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*N1)/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!
