Math Is Fun Forum

Ivar Sand

Member

Registered: 2013-01-22

Posts: 19

The divisibility by 3 rule – direct proof

An integer is said to be divisible by 3 if the remainder of its division by 3 is zero.

The divisibility by 3 rule says that an integer is divisible by 3 if and only if its cross sum is divisible by 3.

This post treats Proof 1 of Theorem 1 of the post The divisibility by 3 rule – proof by induction (b).
The treatment of Proof 1 in that post was sketchy.
Here, we present the theorem in two ways, an informal version and a formal version.

The informal version does not require any knowledge of mathematics except that the reader should have learned the divisibility by 3 rule. The formal version, on the other hand, requires some knowledge of mathematics.

The informal version can be presented orally. I imagine that this could happen at a class reunion of a class where the divisibility by 3 rule has been taught. The proof of the divisibility by 3 rule may not be a popular subject, though, because everybody does not like mathematics. But one could wait until there is a pause in the conversations and then say, "I have something to say" and then just roll it out – don't let anyone get away!

Informal version.
Consider the number 123.
We shall focus on the structure of this number.
We have:
    123 = 1*100 + 2*10 + 3
We use that 100 = 99+1 and 10 = 9+1:
    123 = 1*(99 + 1) + 2*(9+1) + 3
We separate out the parts on the right hand side with 9's in them and put them first:
    123 = (1*99 + 2*9) + (1*1 + 2*1) + 3
We call (1*99 + 2*9) the 9-part of 123 and (1*1 + 2*1) the 1-part:
    123 = 9-part of 123 + 1-part of 123 + 3
We observe that the sum of the 1-part of 123 and 3, noting that 3 is the last digit of 123, is the cross sum of 123:
    123 = 9-part of 123 + cross sum of 123
If we now stop and think for a minute we see that our analysis works for any integer x with any number of digits.
Therefore, we have shown that:
    x = 9-part of x + cross sum of x
We apply the divisibility condition to either side of this equation:
    the divisibility of x by 3 = the divisibility of (9-part of x + cross sum of x) by 3
We observe that the 9-part of x is divisible by 3 so that this part does not contribute to the remainder of the division of (9-part of x + cross sum of x) by 3, so it does not contribute to the divisibility of (9-part of x + cross sum of x) by 3 either.
Therefore, we can remove the 9-part of x from the equation to get:
    the divisibility of x by 3 = the divisibility of (cross sum of x) by 3
Voila, our "proof" is finished!

Formal version.
Let x be a positive integer, x >= 0.
Let x have n digits, n >= 1.
Let xi be digit number i of x, where the numbering goes from right to left and the index value of the utmost digit to the right is 0.

Define
    "y"⌃i = y...y
where i >= 1 and the integer y...y consists of i digits all of which are equal to y.

We have that:
    10⌃i = 10...0
where i >= 0 and 10...0 has i zeroes.
Note that:
    10⌃i - 1 = 9...9
where i >= 1 and the integer 9...9 has i digits so that:
    10⌃i - 1 = "9"⌃i
according to the definition of "y"⌃i above.

Theorem.
Let x be a positive integer, x >= 0.
Let x have n+1 digits where n >= 0.
Let the digits of x be signified by xi where 0 <= i <= n.

Then x is divisible by 3 if and only if the cross sum of x is divisible by 3.

Proof.
First note the following:
The mod function or the modulo operation (a) produces the remainder of a division.
It is termed: x mod y, where x is the dividend and y is the divisor.
So, that an integer x is divisible by 3 is equivalent to saying that x mod 3 = 0.
Therefore, we define:
    the divisibility of x by 3 = (x mod 3 = 0).

We have:
    x = sum(i=0,... n) xi * 10⌃i
    = sum(i=0,... n) xi * ((10⌃i - 1) + 1)
    = sum(i=0,... n) xi * (10⌃i - 1) + sum(i=0,... n) xi * (1)
    = sum(i=1,... n) xi * "9"⌃i + sum(i=0,... n) xi
    = 3 * sum(i=1,... n) xi * "3"⌃i + sum(i=0,... n) xi    as we observe that "9"⌃i = 3 * "3"⌃i

We now introduce the mod function on both sides of the preceding equation:
    x mod 3 = (3 * sum(i=1,... n) xi * "3"⌃i + cross sum of x) mod 3    as we note that sum(i=0,... n) xi equals the cross sum of x
    = (cross sum of x) mod 3                                        as the expression 3 * sum(i=1,... n) xi * "3"⌃i does not contribute to the remainder of the division by 3 (as implied by the mod function) because this expression is divisible by 3

Now, suppose that the cross sum of x is divisible by 3.
This means that (cross sum of x) mod 3 = 0.
The equation:
    x mod 3 = (cross sum of x) mod 3
gives that x mod 3 too is equal to zero.
Therefore, x is divisible by 3.
So, we have proved that the cross sum of x being divisible by 3 implies that x is divisible by 3.

Next, suppose that x is divisible by 3.
This means that x mod 3 = 0.
The equation:
    x mod 3 = (cross sum of x) mod 3
read from right to left gives that (cross sum of x) mod 3 too is equal to zero.
Therefore, the cross sum of x is divisible by 3.
So, we have proved that x being divisible by 3 implies that the cross sum of x is divisible by 3.

All in all, we have proved that x being divisible by 3 is equivalent to the cross sum of x being divisible by 3.
QED

References.
(a) Modulo https://en.wikipedia.org/wiki/Modulo.
(b) The divisibility by 3 rule – proof by induction https://www.mathisfunforum.com/viewtopic.php?id=19234.

---

I majored in Physics in 1976. Also, I studied mathematics and computer science. I worked as a computer programmer. I became a pensioner in 2016. I am from Norway.

Jai Ganesh

Administrator

Registered: 2005-06-28

Posts: 51,603

Re: The divisibility by 3 rule – direct proof

Divisibility Rules.

---

It appears to me that if one wants to make progress in mathematics, one should study the masters and not the pupils. - Niels Henrik Abel.

Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.