Math Is Fun Forum

Ivar Sand

Member

Registered: 2013-01-22

Posts: 21

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 digits where n >= 1.

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-1) xi * 10⌃i
    = sum(i=0,... n-1) xi * ((10⌃i - 1) + 1)
    = sum(i=0,... n-1) xi * (10⌃i - 1) + sum(i=0,... n-1) xi * (1)
    = sum(i=1,... n-1) xi * "9"⌃i + sum(i=0,... n-1) xi
    = 3 * sum(i=1,... n-1) xi * "3"⌃i + sum(i=0,... n-1) 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-1) xi * "3"⌃i + cross sum of x) mod 3    as we note that sum(i=0,... n-1) xi equals the cross sum of x
    = (cross sum of x) mod 3                                        as the expression 3 * sum(i=1,... n-1) 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

We have:
    x mod 3 = (cross sum of x) mod 3
which gives:
    x mod 3 <=> (cross sum of x) mod 3        by Equivalence and Equality are the same in Bool (c)
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.
(c) Equivalence and Equality are the same in Bool https://www.mathisfunforum.com/viewtopic.php?id=35010.

Last edited by Ivar Sand (Yesterday 20:40:21)

---

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: 53,886

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.

Ivar Sand

Member

Registered: 2013-01-22

Posts: 21

Re: The divisibility by 3 rule – direct proof

The divisibility by 3 rule can be repeated, as shown by the following theorem:

Theorem 2.
Let x be an integer, x >= 0.
Let x have n digits where n >= 1.
Let m be an integer, m >= 1.

Then:
    x is divisible by 3 if and only if cross sum**m (x) is divisible by 3
where m is the number of iterations (1) of the cross sum function.

Proof.
We apply proof by induction (2).

The base case of proof by induction, m = 1, is true by Theorem above.

What remains to prove is the induction case of proof by induction, which says that if the theorem holds for any given case m = i, it holds for m = i+1.

So, we assume that the theorem holds for m = i.
This means that:
    x is divisible by 3 if and only if cross sum**i (x) is divisible by 3

We note that cross sum**i (x) satisfies:
    cross sum**i (x) is a positive integer as cross sum**i (x) >= 0.
    cross sum**i (x) have n' digits where n' >= 1.
Then Theorem gives:
    cross sum**i (x) is divisible by 3 if and only if the cross sum of cross sum**i (x) is divisible by 3
in other words:
    cross sum**i (x) is divisible by 3 if and only if cross sum**(i+1) (x) is divisible by 3.
This gives
    cross sum**i (x) is divisible by 3 = cross sum**(i+1) (x) is divisible by 3    by reference (3) by noting that either side of the equal sign is a Boolean value

We have that the theorem holds for m = i:
    x is divisible by 3 if and only if cross sum**i (x) is divisible by 3
Therefore:
    x is divisible by 3 if and only if cross sum**(i+1) (x) is divisible by 3 by replacing "cross sum**i (x) is divisible by 3" by "cross sum**(i+1) (x) is divisible by 3"
This is what we set out to prove, and the proof is complete.

References.
(1) Iterated function https://en.wikipedia.org/wiki/Iterated_function.
(2) Mathematical induction https://en.wikipedia.org/wiki/Mathematical_induction.
(3) Equivalence and Equality are the same in Bool https://www.mathisfunforum.com/viewtopic.php?id=35010.

---

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.