## 4.3   Divisibility Tests

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:

8456352 = 2 · 100 + 5 · 101 + 3 · 102 + 6 · 103 + 5 · 104 + 4 · 105 + 8 · 106.

The divisibility test then arises by replacing each power of 10 with its remainder modulo 3. We saw that

10n 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:

Your browser does not support java.

Can you connect the result of this calculation with the test for divisibility by 3?

#### Research Question 3

Devise a test for divisibility by 9.

Let's now construct a test for divisibility by 11. Using our applet, we get:

Your browser does not support java.

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 2

Prove 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 3

The 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

 64368 8 · 1 + 6 · (–1) + 3 · 1 + 4 · (–1) + 6 · 1    (mod 11) 7    (mod 11).

Explain why the two versions of the divisibility test for 11 are actually the same.

#### Research Question 4

Devise a test for divisibility by 37.

#### Research Question 5

The 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 4

Justify 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.

Section 4.1 | Section 4.2 | Section 4.3 | Section 4.4 | Section 4.5