The Case of the Special Multiplier to Test Divisibility
r=1 implies N=10q+1
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:
Question 1: Any idea why this algorithm works for the number 7? Any idea why 2 is the special multiplier?
- 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 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=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 beq=(N-1)/10
The desired algorithm for computing M, given N relatively prime to 10, is thusR:=N(mod 10)
Case R=1 : X:=1
R=3 : X:=7
R=7 : X:=3
R=9 : X:=9
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!