Is There a Trick to Check if a Number is Divisible by 3?

[Unicyclist]

Okay, this may be a silly subject for a thread, but do you know that trick where you check whether a number is divisible by 3? The one where you add all the digits of that number, then add all the digits of the number you get as a result and so on, until you're left with a single-digit result. If the result is 3, 6 or 9, the number is divisible by 3.

Example 1: 4182
4 + 1 + 8 + 2 = 15
1 + 5 = 6 => 4182 is divisible by 3

Example 2: 9758
9 + 7 + 5 + 8 = 29
2 + 9 = 11
1 + 1 = 2 => 9758 is not divisible by 3

Does anybody know why this works and how you can prove it, other than by trial and error? I've always considered this a rather neat trick, but could never figure out how it works.


p.s. Well, yeah it's divisible, but 3 is not a factor of the number, so you won't get an integer as your result.

 

[matt grime]

You can't prove it by trial and error. There are an infinite number of things to check. Proofs don't work like that. It is one of the first things you prove in number theory - look at the reaminder mod 3. All you need is for the result to be divisble by 3 at some stage to stop - so if you hit 12 there's no need to carry on.

It works becuase 10 leaves remainder 1 on division by 3. See, there is a point to the arithmetic you learned in primay/elementary/junior school

 

[Integral]

First consider the 2 digit case.

Consider some 2 digit number ab. We are give that a+b = 3m where m is some interger.

We need to show that

10a + b has 3 as a factor.
let 10a +b = N where N is some integer

from a + b = 3m we have
b = 3m -a

so

10a + (3m -a) = N .

9a + 3m = N

3(3a+m) = N

Since N is an integer we have shown that it has factors 3 and (3a+m).

 

[Unicyclist]

Hey, that's a really nifty proof, Integral.

Can you prove the opposite? If digits don't add up to a multiple of 3, the number doesn't have 3 as a factor.

 

[matt grime]

Yes. I told you how to do that - modulo arithmetic. 10=1 mod 3 whcih is to be read as '3 divides 10 with remainder 1' just like you did in primary/junior/elementary school*, so mod 3 the number

abcdeg..h =a+b+c+..+h mod 3

where each of those is a digit in the thedecimal expansion.* this is an example of how people often get mathematical sophistication the wrong way round. Writing sqrt(2)=1.41 (2 d.p) is incredibly unsophisticated.

 

[DyslexicHobo]

Is there any other tricks like that? I had forgotten all about that!

Very neat.

 

[HallsofIvy]

A number is divisible by 2 if and only if its last digit (units digit) is divisible by 2. 103212334 is divisible by 2 because its last digit, 4, is divisible by 2.
1232121 is not divisible by 2 because its last digit, 1, is not.

A number is divisible by 3 if and only if the sum of its digits is divisible by 3.
322311 is divisible by 3 because the sum of its digits, 12, is divisible by 3.

A number is divisible by 4 if and only if ithe number formed by its last two digits is divisible by 4. 1236 if divisible by 4 because 36 is divisible by 4. 12314 is not divisible by 4 because 14 is not divisible by 4.

A number is divisible by 5 if and only if its last digit is either a 5 or a 0.
12312345 and 1336340 are divisible by 5 but 31232323243 is not.

A number is divisible by 6 if and only if it is divisible by both 2 and 3. 213342 is divisible by 6 because its last digit, 2, is divisible by 2 and the sum of its digits, 15, is divisible by 3.
A nuimber s divisible by 7 if and only if the number formed by adding 5 times its last digit to the number formed by the other digits is divisible by 7. 3220 is divisible by 7 because the number formed by adding 5 times its last digit, 0, to the other digits, 322, is divisible by 7 (and we know that because 2*5+ 32= 42 is divisible by 7).

A number is divisible by 8 if and only if the number formed by its last 3 digits is divisible by 8. 1232323264 is divisible by 8 because 264= 8*33 is divisible by 8.

A number is divisible by 9 if and only if the sum of its digits is divisible by 9. 3375 is divisible by 9 because the sum of its digits, 18, is divisible by 9.

A number is divisible by 10 if and only if its last digit is a 0. 232323230 is divisible by 10 because its last digit is 10.

A number is divisible by 11 if and only if the difference between the sum of the odd digits and the sum of the eveh digits is divisible by 11. 25564 is divisible by 11 because the difference between the sum of its odd digits, 2+ 5+ 4= 11, and the sum of its even digits, 5+ 6= 11, which is 11-11= 0, is divisible by 11.

 

[Unicyclist]

Wow, HallsofIvy! Really impressive!

Also, a number is divisible by 1 and there's no if.

 

[Gib Z]

Hey guys I know you hear this too often but sorry to raise an old thread :P I just thought it was quite related, and I think the solution to my problem has already been answered in one of matt grimes posts where he says the thing works because in base 10, mod 9 gives a remainder 1 and stuff but I'm really new to the modular arithmetic thing and I don't understand any of this!

Well here's my requests and question :)

Well the original thing was proving why summing the digits works as a divisiblity test for 3, and matt said "It works becuase 10 leaves remainder 1 on division by 3". I know the same argument passes for 9 as well, but I don't really understand why it leaving a remainder of 1 is significant? Sorry about that >.<

Well basically the formal question is:

"Prove that the remainder left when a positive integer n is divided by 9 is the same as the number obtained by repeatedly replacing n with the sum of its digits."

No idea? Thanks a lot by the way guys.

 

[matt grime]

Write out the definition of a decimal expansion: if I have a number whose decimal expansion is the string

x_nx_{n-1}\ldots x_1x_0

what does that mean in terms of adding up multiples of powers of 10?

 

[Gib Z]

\sum_{k=0}^{n} x_k \cdot 10^k

I'm sorry for my slowness, but i don't see how that helps >.<

 

[matt grime]

reduce it mod 3 (or 9) and what do you have? (You can also reduce mod 11 to find the alternating sum of digits trick mentioned above.)

 

[Gib Z]

Ok I'm not too sure what I'm doing is in any way valid, but here:

Lets take one partial sum, x_n * 10^n. Mod 3 of 10^n is 1, but What about the x_n? I get the feeling somehow its x_n that's meant to be left over, since were summing them all, but why? Doesn't x_n get "modded" as well?

 

[matt grime]

You may reduce, or not reduce, any individual term at any time as you see fit when doing modulo arithmetic. Just as you may wish to work with 2/4 rather than 1/2 if it makes some simplification easier.

The simple fact is that when you reduce something mod 3 you get precisely the same as you get when reducing the sum of the digits mod 3, so one is 0 mod 3 if and only if the other is 0 mod 3 (or 9).

 

[Edgardo]

Hello Unicyclist,

you can prove the divisibility rule by induction. The proof goes like this:

1) First we are going to show the following:
Lemma
10^k-1 is divisible for all k \in \mathbb{N}.
Proof by induction
(i) The basis
k=1:
10^1-1 = 9 is divisible by 3.

(ii) The inductive step
Assumption: Let 10^k-1 be divisible for one natural number k.
Then
10^{k+1}-1 = 10 \cdot 10^k -1 = (9+1) \cdot 10^k -1 = 9\cdot 10^k + 1\cdot 10^k -1
=9 \cdot 10^k + \underbrace{(10^k-1)}_{assumption}
is divisible by 3. 2) In the next step we are going to use the lemma to prove the divisibility rule:
Theorem
Let z be a natural number that is represented by
z = \sum_{k=0}^{n} a_{k} 10^k where a_k are natural numbers from 0 to 9.

If \sum_{k=0}^{n} a_k is divisible by 3 then z is also divisible by 3 ("divisibility rule").

Proof
z=\sum_{k=0}^{n} a_k 10^k = \sum_{k=0}^{n} a_k (10^k-1+1) = \sum_{k=0}^{n} a_k (10^k-1) + \sum_{k=0}^{n} a_k

= \sum_{k=1}^{n} a_k (10^k-1) + \sum_{k=0}^{n} a_k

Since \sum_{k=1}^{n} a_k (10^k-1) is divisible by 3 according to our Lemma and \sum_{k=0}^{n} a_k is divisible by 3,
it follows that z is divisible by 3.

 

[arkhammedos]

we can use conguruence as in the first one:4182
$4182=4\cdot10^{3}+10^{2}+8\cdot10+2$
so $4182 \equiv 1+1+2+2 \equiv 0$ (mod 3).
sory for my bad english.

 

[matt grime]

PLease read the guide on how to use tex. Click on any piece of tex'ed mathematics to see the code needed to create it. $ and $$ are not the correct delimiters.

4182=4\cdot10^{3}+10^{2}+8\cdot10+2

click to find code. inline needs itex and not tex in the opening/closing tags.