𝔉𝔲𝔯𝔪𝔞𝔫 𝔘𝔫𝔦𝔳𝔢𝔯𝔰𝔦𝔱𝔶 Electronic Journal of Undergraduate Mathematics Volume 3, 1997 1-5

DIVISIBILITY TESTS

APOORVA KHARE

Abstract. In this paper, we give a new method to test the divisibility of any positive integer by another. First, we outline the usual test, in which one proceeds from right to left, i.e. the direction opposite the one taken while carrying out long division. After pointing out some of the problems with this method, we give another method, which forms the core of this paper. This latter method works along the same lines as the earlier one, but here one proceeds from left to right. Examples of some well known divisibility tests for special divisors are given along with some other observations. Finally, we generalize our divisibility test to any integer base greater than 1.

1. Introduction

We are all familiar with divisibility tests for certain divisors such as 3, 9, and 11. In these tests, one examines the weighted sum of the digits of the dividend i.e. the digits are multiplied by a fixed set of weights which depend on the divisor. For example, to test divisibility by 3, one multiplies the first digit by 1, the second digit by 1, and so on proceeding from right to left. At the end, one adds up the products (because the set of weights or coefficients for 3 comprise the period 1 sequence 1, 1, …). To test divisibility by 9, one does the same thing because the weights for 9 also comprise the same sequence 1, 1, …. For 11, the corresponding sequence of weights is 1, −1, 1, −1, … (a period 2 sequence).

A question that naturally arises is “How does one find the sequence of weights for the various divisors?” As it turns out, the answer is quite simple, however, we shall see that this standard “right-to-left” method can be substantially improved for certain divisors, in that the sequence of weights given by the method just described is not always the best choice.

Throughout the paper, unless otherwise stated, all variables denote positive integers. As customary, we denote the set {1, 2, 3, … } of positive integers by Z^{+}.

2. The Standard Test

Given a positive integer s, write

s = ∑_{j=0}^{m} s_{j}10^{j}

Received by the editors March 6, 1997.

1991 Mathematics Subject Classification. 11A.

Key words and phrases. Divisibility Tests.

The author would like to Dr. David M. Bradley for his valuable suggestions which helped in improving the manuscript.

where s_{0}, s_{1}, …, s_{m} are the digits of s in base 10. More generally, we define

s^{←}(k) = ∑_{j=0}^{m} s_{j}k^{j},

so that s = s^{←}(10). To test whether s is divisible by d ∈ Z^{+}, let k ≡ 10 mod d, |k| minimal. Then

s ≡ s^{←}(10) ≡ s^{←}(k) mod d

and thus s is divisible by d if and only if s^{←}(k) is, i.e. the sequence of weights is simply k^{0}, k^{1}, k^{2}, …, where

k = k_{d}^{←} ≡ 10 mod d.  (1)

This is fine as long as 1 ≤ d ≤ 19. However, for d ≥ 20, this method yields k = 10, which amounts to simply testing s itself. Admittedly, the powers of 10 can be reduced modulo d, but the simplicity of the test lies essentially in the smallness of |k|. We address this problem in the next section, where an alternative method is given which produces smaller k’s for certain divisors.

3. A New Test

Again, given s ∈ Z^{+}, write

s = ∑_{j=0}^{m} s_{j}10^{j},

where s_{0}, s_{1}, …, s_{m} are the base 10 digits of s. We shall suppose that d ∈ Z^{+} is coprime to both 2 and 5. Then 10 has a multiplicative inverse modulo d, and we shall take k to be the representative of least absolute value. Thus, 10k ≡ 1 mod d and |k| is minimal. Then

s ≡ ∑_{j=0}^{m} s_{j}10^{j} ≡ ∑_{j=0}^{m} s_{j}k^{−j} ≡ 10^{m}( ∑_{j=0}^{m} s_{j}k^{m−j}) mod d.  (2)

Since d has no factors in common with 10, it follows that s is divisible by d if and only if

s^{→}(k) = ∑_{j=0}^{m} s_{j}k^{m−j}

is, i.e. the sequence of weights (proceeding right to left this time) is simply k^{0}, k^{1}, k^{2}, …, where

k = k_{d}^{→} ≡ 10^{−1} mod d.  (3)

Observe that we can also use (2) to compute s mod d even when s is not divisible

by d. We simply reduce 10^{m} mod d and multiply the result by s^{→}( k_{d}^{→}) mod d.

As an example of our new divisibility test, note that k^{→}_{19} = 2. So, to test whether 36461 is divisible by 19 or not, we compute \overrightarrow{36461}(2) = (3 × 2^{0}) + (6 × 2^{1}) + (4 × 2^{2}) + (6 × 2^{3}) + (1 × 2^{4}) = 3 + 12 + 16 + 48 + 16 = 95. Repeating the operation, \overrightarrow{95}(2) = (9 × 2^{0}) + (5 × 2^{1}) = 9 + 10 = 19. Since 19 ≡ 0 mod 19, 95 ≡ 0 mod 19. Since 95 ≡ 0 mod 19, 36461 ≡ 0 mod 19. Note that the standard method is much more unwieldy in this case, since there, k^{←}_{19} = 10 or −9.

Table 1

Standard Test New Test
d  k_{d}^{←}  k_{d}^{→}
1  1  1
3  1  1
7  3  -2
9  1  1
11  -1  -1
13  -3  4
17  -7  -5
19  -9  2
21  10  -2
23  10  7
27  10  -8
29  10  3
31  10  -3

In Table 1, we give a few values of d and the corresponding k_{d}-values obtained from the two methods.

Sometimes it is impractical to use this method because finding the (reduced) powers of k is tedious for large k (as examples, k^{→}_{93} = 28, k^{→}_{77} = 54 etc.) However, this method is certainly of theoretical importance because even in these cases, the problem of divisibility testing can be solved in exactly the same way.

The process can sometimes be shortened if we consider every number to be of the form 10x + y with 0 ≤ y ≤ 9. For example, if s = 10x + y is divisible by 7, then x + 5y must also be divisible by 7, and conversely. This is true for all positive integer values of x. So, for example, to test whether 336 is divisible by 7 or not, we put x = 33, y = 6. We now test 33 + (6 × 5) = 33 + 30 = 63. Since 7 divides 63, it follows that 7 also divides 336. Alternatively, instead of testing x + 5y for divisibility by 7, it is equivalent to test x − 2y. Thus 336 is divisible by 7 because 33 − (2 × 6) = 21 is divisible by 7.

4. Divisibility Test for a General Base

It is easy to see how to extend the ideas of the previous section, which used the decimal system of representing numbers, to a divisibility test which works in any integer base greater than 1 which is coprime to the divisor d. Simply replace the number 10 in the definition (3) with the base in question.

Recall (section 1) that in base 10, the set of weights for divisibility by 9 and 3 comprise the same period 1 sequence consisting of all ones. The following theorem explains this phenomenon.

Theorem 1. Let B > 1 and d be positive integers such that d|B − 1. Then we

may take k_{d}^{→} = k_{d}^{←} = 1.

Proof. Since d|B − 1, we have

k_{d}^{←} ≡ B ≡ 1 mod d

It follows that

k_{d}^{→} ≡ B^{−1} ≡ 1 mod d

also.□

Thus, for example, when B = 10, we may take k_{9} = k_{3} = 1.

The following theorem is useful for determining the relevant k_{d}^{→} -values for general bases.

Theorem 2. Let a and B be coprime positive integers with a < B. Let m be a positive integer and d = Bm + a. In analogy with (3), let

k_{d}^{→} ≡ B^{−1} mod d.

Then

k_{d}^{→} ≡ k_{a}^{→}+ml mod d,  (4)

where l = (B k_{a}^{→}−1)/a.

Remark 1. The Theorem says, in effect, that we can test divisibility by any number whose unit’s digit is coprime to the base. Equation (4) can help us to

calculate all k_{d}^{→} -values easily if we know the k_{a}^{→}-values for all possible base B digits which are coprime to B.

Remark 2. Note that we require a and B to be coprime in order that B have an inverse modulo d. Of course, if a and B are not coprime, then their greatest common divisor can be factored out of d and tested separately. Thus, in base 10, it is customary to test divisibility by an even number or a multiple of 5 by first inspecting the unit’s digit of the dividend.

Proof. By definition of k_{a}^{→}, there exists a positive integer l such that

k_{a}^{→}B = 1 + al.

Then

(k_{a}^{→}+ml)B = 1 + al + mlB = 1 + l(a + mB) = 1 + ld.

Thus

(k_{a}^{→}+ml)B ≡ 1 mod d,

and so

k_{a}^{→}+ml ≡ B^{−1} ≡ k_{d}^{→} mod d,

as required.□

Let us apply Theorem 2 to the decimal system. Here, B=10, so that a takes the values 1, 3, 7 and 9. For each value of a, we use (3) to find k_{a}^{→}. Then, using (4), we

obtain the values of k_{d}^{→} given below. We have

k_{d}^{→} = \{ \begin{matrix}9m + 1 & if d = 10m + 1 \\ 3m + 1 & if d = 10m + 3 \\ 7m + 5 & if d = 10m + 7 \\ m + 1 & if d = 10m + 9 \end{matrix}

for all positive integers m.

In Remark 2, we indicated that one typically applies a separate divisibility test when the divisor and the base are not coprime. We conclude the paper by examining this case more carefully.

Suppose d = jp_{1}^{α_{1}}p_{2}^{α_{2}} … p_{h}^{α_{h}}, where j is coprime to B, and p_{1}, p_{2}, … p_{h} are the primes that divide both d and B. Since j is coprime to B, we test for divisibility by j using the method of this paper previously described. For each p_{i} (1 ≤ i ≤ h), we perform the following test:

If β_{i} is the highest power of p_{i} dividing B we check whether or not the number formed by the rightmost ⌊α_{i}/β_{i}⌋+1 base B digits of the dividend is divisible by p_{i}^{α_{i}}. (Here ⌊x⌋ denotes the greatest integer less than or equal to x.) This works because the place value of each of the other digits is ≥ B^{⌊α_{i}/β_{i}⌋+1} > B^{(α_{i}/β_{i})}, which is divisible by p_{i}^{β_{i}(α_{i}/β_{i})} = p_{i}^{α_{i}}. Of course, if α_{i} is divisible by β_{i}, then the number formed by only the rightmost α_{i}/β_{i} digits need be tested, because each of the other digits has a place value ≥ B^{(α_{i}/β_{i})}, which is divisible by p_{i}^{α_{i}}. For example, in base 12, the only prime factors of 12 are 2 and 3 where 12 = 3 × 2^{2}. So, to check divisibility by 8 = 2^{3}, the ⌊3/2⌋+1 = 2 rightmost digits have to be checked. But in the decimal system, 10 = 2×5, so to test for divisibility by 4, the 2 rightmost digits are tested, whereas to test for divisibility by 8, the 3 rightmost digits are tested.

Class XII, B.J.B. College, Bhubaneswar, Orissa, India

   E-mail address: khare@iopb.ernet.in

Sponsor: David Bradley, Centre for Experimental & Constructive Mathematics, Simon Fraser University, Burnaby, B.C., Canada

   E-mail address: dbradley@reno.cecm.sfu.ca