Criteria of divisibility by 9 and 11

Here we shall compare the criterion of the divisibility of an integer by 9 with that of the divisibility by 11 and later learn that similar criteria are carried over to other number systems.

Start with a decimal representation of a positive integer a:

 a = an10n + an-110n-1 + ... + a1101 + a0

Divisibility by 9

 a is divisible by 9 if and only if the sum of the digits an + an-1 + ... + a1 + a0 is divisible by 9.

Divisibility by 11

 a is divisible by 11 if and only if the alternating sum of the digits (-1)nan + (-1)n-1an-1 + ... -a1 + a0 is divisible by 11. In what follows I shall be using representation of a number in various base systems. In the decimal (base 10) system a number a is written as

 a = (a)10 = an10n + an-110n-1 + ... + a1101 + a0

Generally speaking, for an integer base b the same number a will be written as

 a = (a)b = ckbk + ck-1bk-1 + ... + c1b1 + c0

Notation (a)b is meant to underscore the base in which a is expanded. The most customary is the decimal system. But, say, the French still use remnants of the system in base 20. With the advent of computers the binary (base 2) and hexadecimal (base 16) have been thrust into prominence. The octal system (base 8) is very useful in handling lengthy binary representations.

Conversion between different bases is a good exercise that helps test your understanding of relevant techniques. Theorem

Let b be an integer. Then an integer a

1. is divisible by (b-1) if and only if the sum of digits in its expansion (a)b is divisible by (b-1)
2. is divisible by (b+1) if and only if the alternating sum of digits in its expansion (a)b is divisible by (b+1)

Proof

The proof is based on Modulo Arithmetic. Thus we have b-1=0 (mod (b-1)) which implies b=1 (mod (b-1)). Therefore, for every i>0, bi = 1 (mod(b-1)). Multiplying this by ci and summing up for i=0,1, ..., k we get the first assertion.

Similarly, b+1=0 (mod (b+1)) hence b=-1 (mod (b+1)). Therefore, for i>0, bi = (-1)i (mod(b+1)). Multiplying this by ci and summing up for i=0,1, ..., k we get the second assertion.

Example 1

Let a=164. Is it divisible by 4? On the one hand, 164=125+25+2·5+4=(1124)5. The sum of digits is 1+1+2+4=8 and is divisible by 4. Therefore 164 is divisible by 4.

On the other hand, 164=2·81+0·27+0·9+0·3+2=(20002)3. The alternating sum of digits is 2-0+0-0+2=4 and is divisible by 4. Therefore, again, 164 is divisible by 4. For divisibility by 7 there are two criteria:

1. a = (a)6 = ck6k+ck-16k-1+...+c161+c0 is divisible by 7 iff the alternating sum of digits (-1)kck+(-1)k-1ck-1+...+c0 is divisible by 7.
2. a = (a)8=ck8k+ck-18k-1+...+c181+c0 is divisible by 7 iff the sum of digits ck+ck-1+...+c0 is divisible by 7.

Example 2

512=83. Therefore (512)10=(1000)8. This implies that divided by 7 the remainder will be 1. Then, for example, 511 is divisible by 7.

1296=64. Therefore (1296)10=(10000)6. From here (1296+6)10=(10010)6. Its alternating sum of digits is 1-0+0-1+0=0. As a result, 1302 is divisible by 7. • 