Recall how we developed the test for divisibility by 3 in the Prelab section. Suppose we want to calculate the remainder of 8456352 when divided by 3 quickly, and by hand. We think of 8456352 in expanded notation:
The divisibility test then arises by replacing each power of 10 with its remainder modulo 3. We saw that
1 (mod 3)
for all integers
n 
0. Thus,
| 8456352 | = | 2 · 100 + 5 · 101 + 3 · 102 + 6 · 103 + 5 · 104 + 4 · 105 + 8 · 106 |
| |
2 + 5 + 3 + 6 + 5 + 4 + 8 (mod 3) | |
| |
33 (mod 3). |
Repeating the process, we discover that
33
3 + 3 6 (mod 3), which
is easily seen to be congruent to 0 (mod 3). Therefore,
8456352 is divisible by 3.
The key to this process is the values of the powers of 10 taken modulo 3. To deduce similar tests for other potential divisors, we can use the applet below. It produces a list of the values of 10j % n with j running from 0 to M. Let's try it out with n = 3:
Can you connect the result of this calculation with the test for divisibility by 3?
Research Question 3Devise a test for divisibility by 9. |
Let's now construct a test for divisibility by 11. Using our applet, we get:
Note that the sequence appears to be purely
periodic. In fact, we can prove that the sequence is
purely periodic by observing that
102 1 (mod 11), so
that for any integer
k 0 we have
| 10k+2 | |
10k · 102 | (mod 11) |
| |
10k · 1 | (mod 11) | |
| |
10k | (mod 11). |
Since 10k+2
10k (mod 11) for all
k 0, it follows that the
sequence is purely periodic.
This result is not an accident; it will be true if we replace 11 with any prime p other than 2 or 5. So that you won't have any doubts about this assertion, it is left for you to prove in the next exercise.
Exercise 2Prove that the sequence 10 j % p ( j = 0, 1, 2, . . .) is purely periodic for any prime p except 2 and 5. |
From our work above, we now know (as opposed to just suspect) that the values of 10 j % 11 alternate forever, beginning with 1, 10, 1, 10, . . . . On the basis of this, if n = dkdk-1 . . . d1d0 , then
| n | = | d0 · 100 + d1 · 101 + d2 · 102 + d3 · 103 + ··· |
| |
d0 · 1 + d1 · 10 + d2 · 1 + d3 · 10 + ··· (mod 11). |
For example, the test applied to 64368 would be as follows:
| 64368 | = | 8 · 100 + 6 · 101 + 3 · 102 + 4 · 103 + 6 · 104 |
| |
8 · 1 + 6 · 10 + 3 · 1 + 4 · 10 + 6 · 1 (mod 11). | |
| |
117 (mod 11). | |
| |
7 · 1 + 1 · 10 + 1 · 1 (mod 11). | |
| |
18 (mod 11), |
which is obviously congruent to 7 (mod 11).
Thus, we see that 64368 7 (mod 11),
and from this it follows that 64368 is not divisible by 11.
Exercise 3The standard divisibility test for 11 uses multipliers 1 and –1 instead of 1 and 10. In other words, the test applied to 64368 would say that
Explain why the two versions of the divisibility test for 11 are actually the same. |
Research Question 4Devise a test for divisibility by 37. |
Research Question 5The number 7 is infamous for not having a divisibility test. Show that this assertion is false by devising a test for divisibility by 7. |
Exercise 4Justify the standard tests for divisibility by n = 2, 5, and 10. In each of these three cases, the standard test states that a number is congruent to its units (last) digit modulo n. |