divisibility

Proof for the divisibility test of 3

This post is a bit mathematical, and talks about the divisibility test of 3 we all learnt in high school. As I’m not aiming for brevity but for completeness and ease of explanation let me remind you all of the theorem involved to test the divisibility of a number by 3 and then move onto its proof.

To test the divisibility of a number N by 3, recursively sum the digits that make up the number till you reach a manageable number whose divisibility of 3 can be inferred trivially.

For example if we’re testing the divisibility of 3423 by 3, we’ll add up 3+4+2+3 and check if that sum is divisible by 3. We know that 12 is divisible by 3, hence the number 3423 is divisible by 3 as well . If we did not know that 12 was divisible by 3 we would have summed up the digits of 12 and and try to see if that sum is divisible by 3 and so on.

Proof for theorem:

The main crux of the proof is representing the number as a specific set of additions and multiplications and your work is almost done. If we have a number N with n digits a_{1}a_{2} \ldots a_{n}, then the number N can also be represented as follows

N = a_1 \cdot 10^{n-1} + a_2 \cdot 10^{n-2} + ... + a_n \cdot 1

With out proof in mind let’s separate the sum of all the digits of N i.e, a_1 + a_2 + \ldots + a_n and see what we get.

N = \left(\underbrace{99\ldots9}_{n\text{-times}} \cdot a_1 + \underbrace{99\ldots9}_{n-1\text{-times}} \cdot a_2 + \ldots 9 \cdot a_{n-1} \right) + \left( a_1 + a_2 + \ldots + a_n \right)

Now if we can prove that the right glob we have here is divisible by 3 then our job is done (We’ll know that the if the sum of its digits is divisible by 3 then N is divisible by 3).

Corollary #1:

A number with just 9 as its digits is divisble by 3

Proof for Corollary #1:

We know that any number which is divisible by 9 is divisible by 3 as well \left(3 * 3 = 9\right). So a number M which has m digits in it and all m digits are 9 can be represented as

\underbrace{99\ldots9}_{m\text{-times}} = 9 \cdot 10^{m-1} + 9 \cdot 10^{m-2} + ... + 9

On further simplification we get

\underbrace{99\ldots9}_{m\text{-times}} = 9 \left(10^{m-1} + 10^{m-2} + ... + 1\right)

The above proves the corollary. With the corollary proven we can concur that the sum of the digits of a number should also be divisible by 3 if a number is divisible by 3 and vice versa.

Acknowledgement: I first saw this proof on the One Mathematical Cat website, but the instructor just proved it for a specific case of 3 digits. This was my effort in generalizing the proof for any arbitrary number of digits.

Advertisement