Divisibility by 3 Proof

This week I’m going to take a break from presidential trivia and try something new. I have always enjoyed a good mathematical proof. Until I run out of ideas, I’ll go through some famous mathematical theorems and try to explain why they are true in as layman’s terms as possible. To start, this week I will show that if the sum of the digits of any integer is divisible by 3, then the whole number is divisible by 3. However, before we get to that I present the usual weekly logic puzzle.

Logic Puzzle

Four cards are on a table. You can see that face up cards are labeled D, K, 3 and 7. You know that every card has a letter on one side and a number on the other. There is supposed to be a manufacturing rule that a card that has a D one side must have a 3 on the other. Which two cards must you turn over to verify this rule was followed?

The answer will be at the end of the newsletter.

Divisibility by 3 Proof

As stated in the introduction, one can test if an integer is evenly divisible by 3 as follows:

1. Take the sum of the digits.
2. If the sum from rule 1 is evenly divisible by 3, then the original will be also. Also, if the sum is not divisible by 3, nor will the original number be.

 

Let’s look at the White House phone number, for example, which is 2024567041. The sum of the digits is 2+0+2+4+5+6+7+0+4+1 = 31. 31 is not divisible by 3, thus the original number is not either.

To prove this works, break down the original number as follows:

2024567041 = (2*1000000000) + 0 + (2*10000000) + (4*1000000) + (5*100000) + (7*1000) + 0 + (4*10) + (1*1)

Next, separate the powers of 10 into two parts, a 1 and the rest of the number:

= (2*(999999999+1)) + 0 + (2*(9999999+1)) + (4*(999999+1)) + (5*(99999+1)) + (7*(9999+1)) + 0 + (4*(9+1)) + (1*(0+1))

It’s obvious that any number with all 9’s is evenly divisible by both 3. For example, 99999 = 3 * 33333.

That said, let’s rearrange the terms in the number above.

= (2*999999999) + (2*9999999) + (4*999999) + (5*99999) + (7*9999) + (4*9) + (1*0) + (2*1) + (2*1) + (4*1) + (5*1) + (7*1) + (4*1) + (1*1)

Every term in the first seven terms are obviously evenly divisible by 3 because they divide evenly by a number with all 9’s. I other words, (2*999999999) + (2*9999999) + (4*999999) + (5*99999) + (7*9999) + (4*9) + (1*0) is evenly divisible by 9, so we can remove that part. Leave us with:

(2*1) + (2*1) + (4*1) + (5*1) + (7*1) + (4*1) + (1*1) = 2+0+2+4+5+6+7+0+4+1 = 31

This is the sum of the digits, which equals 31. Since this leftover part does not divide evenly by 3, the entire number can’t either.

This same rule is also can test for divisibility by 9. If the sum of digits of the original number is divisible by 9 then so will the entire number. The converse is also true, if the sum of digits is not evenly divisible by 9, then the entire number won’t either.

Logic Puzzle Solution

Let’s call the rule that 3 must be on the opposite side of a D rule the “D-3” rule.

1. • It’s obvious we must turn over the D card to ensure the other side is a 3.
2. • The other side of the K card must have a number. Since, the other side can’t have a D, then this card does not help us disprove the D-3 rule was followed.
3. • The other side of the 3 card must have a letter. If that letter is a D, it supports the D-3 rule. If any other letter is on the other side, it doesn’t help us. So, either this card will comply with the D-3 rule or not be relevant. Either way, we are looking for a card that breaks the rule to invalidate the D-3 rule. Whatever letter is on the other side won’t disprove the D-3 rule. So, it doesn’t need to be checked.
4. • The other side of the 7 card must have a letter. If that letter were a D, then that card would disprove the D-3 rule. So, it must be checked to ensure it is not a D-7 card, which would be a contraction of the D-3 claim.

 

Thus, the D and 7 cards are the only ones that must be checked.