Proofs of Divisibility Tests

Here is a basic fact: Suppose you have a positive integer x which, when you write its digits, looks like:

am · · · a4a3a2a1a0.

So a0  is the digit in the one’s place, a1  is the digit in the 10’s place, a2  is the digit in the 100’s place, etc. Then the number x equals

x  =  a0 + a1 · 10 + a2 · 100 + a3 · 1000 + a4 · 10000 + · · · + am · 10m

=  a0 + a1 · 10 + a2 · 102 + a3 · 103 + a4 · 104 + · · · + am · 10m.

Most of the divisibility tests and their proofs come from examining this expression mod

n for some n, and replacing the various powers of 10 with their equivalents mod n:

1.    Proof of Test for Divisibility by 2. Observe that 10 divided by 2 has a remainder of 0.

So 10 ≡ 0 (mod 2). Then 10k ≡ 0k ≡ 0 (mod 2) for k = 1, 2, 3, . . .. Hence

x  ≡  a0 + a1 · 0 + a2 · 0 + a3 · 0 + a4 · 0 + · · · + am · 0

≡  a0 (mod 2).

Therefore x is divisible by 2 if and only if its last digit a0 is divisible by 2, which happens if and only if the last digit is one of 0, 2, 4, 6, 8.

2.    Proof of Test for Divisibility by 4. Observe that 100 divided by 4 has a remainder of 0. So 100 ≡ 0 (mod 4). Hence 10k ≡ 0 (mod 4) for k = 2, 3, 4, . . .. Then

x  ≡  a0 + a1 · 10 + a2 · 0 + a3 · 0 + a4 · 0 + · · · + am · 0

≡  a0 + a1 · 10 (mod 4).

Therefore x is divisible by 4 if and only if the number a0 + a1 · 10 is divisible 4. But a0 + a1 · 10 is the number formed by keeping only the last two digits of x. So x is divisible by 4 if and only if the number formed by dropping all but the last two digits of x is divisible by 4.

3.    Proof of Test for Divisibility by 9. Observe that 10 divided by 9 has a remainder of 1.

So 10 ≡ 1 (mod 9). Hence 10k ≡ 1k ≡ 1 (mod 9) for k = 1, 2, 3, 4, . . .. Then

x  ≡  a0 + a1 · 1 + a2 · 1 + a3 · 1 + a4 · 1 + · · · + am · 1

≡  a0 + a1 + a2 + a3 + · · · + am (mod 9).

Therefore x is divisible by 9 if and only if the sum of its digits is divisible by 9.

4.    Proof of Test for Divisibility by 10. Observe that 10 divided by 10 has a remainder of 0. So 10 ≡ 0 (mod 10). Hence 10k ≡ 0k ≡ 0 (mod 10) for k = 1, 2, 3, . . .. Then

x  ≡  a0 + a1 · 0 + a2 · 0 + a3 · 0 + a4 · 0 + · · · + am · 0

≡  a0 (mod 10).

Therefore x is divisible by 10 if and only if its last digit a0  is divisible by 10, which happens if and only if the last digit is 0.

5.    Proof of Test for Divisibility by 11. Observe that 10 ≡ −1 (mod 11). Hence 10k ≡

(−1)k (mod 11) for k = 1, 2, 3, 4, . . .. Then

x  ≡  a0 + a1 · (−1) + a2 · (−1)2 + a3 · (−1)3 + a4 · (−1)4 + · · · + am · (−1)m

≡  a0 − a1 + a2 − a3 + a4 + · · · + am(−1)m (mod 11).

Therefore x is divisible by 11 if and only if alternating sum of its digits a0 − a1 + a2 −

a3 + a4 + · · · + am(−1)m  is divisible by 11.

6.    Proof of Test for Divisibility by 12. Since 12 = 223 involves more than one prime, let’s start a different way. If a number is divisible by 12, then in its prime factorization it must contain 223, possibly along with other prime factors (perhaps even some more 2’s and 3’s). Therefore the number must be divisible by both 3 and 4. Conversely, if a number is divisible by both 3 and 4, then in its prime factorization it must contain 223, possibly along with other prime factors (perhaps even some more 2’s and 3’s). Therefore, a number is divisible by 12 if and only if it is divisible by both 3 and 4, and this is our divisibility test.