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 · 10 ^{0}+ 5 · 10^{1}+ 3 · 10^{2}+ 6 · 10^{3}+ 5 · 10^{4}+ 4 · 10^{5}+ 8 · 10^{6}.The divisibility test then arises by replacing each power of 10 with its remainder modulo 3. We saw that

10 ^{n}1 (mod 3)for all integers

n0. Thus,

8456352 = 2 · 10 ^{0}+ 5 · 10^{1}+ 3 · 10^{2}+ 6 · 10^{3}+ 5 · 10^{4}+ 4 · 10^{5}+ 8 · 10^{6}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 10

^{j}%nwithjrunning from 0 toM. Let's try it out withn= 3:

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:

Note that the sequence appears to be purely periodic. In fact, we can

provethat the sequence is purely periodic by observing that 10^{2}1 (mod 11), so that for any integerk0 we have

10 ^{k+2}10 ^{k}· 10^{2}(mod 11) 10 ^{k}· 1(mod 11) 10 ^{k}(mod 11). Since 10

^{k+2}10^{k}(mod 11) for allk0, 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

pother 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 primepexcept 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, ifn=d, then_{k}d_{k-1}. . . d_{1}d_{0}

n= d_{0}· 10^{0}+d_{1}· 10^{1}+d_{2}· 10^{2}+d_{3}· 10^{3}+ ···d_{0}· 1 +d_{1}· 10 +d_{2}· 1 +d_{3}· 10 + ··· (mod 11).For example, the test applied to 64368 would be as follows:

64368 = 8 · 10 ^{0}+ 6 · 10^{1}+ 3 · 10^{2}+ 4 · 10^{3}+ 6 · 10^{4}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 modulon.

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

Copyright © 2001 by W. H. Freeman and Company