**The magical number 3**

So I was there, hacking away with my buddy of the day, an Ingress player I found on the Resistance channel around lunch time and that I decided to team up with for a couple of hours; when, just after having revealed that I do maths, he asked me "So what about the number 3 ? Why is it a magical number ?". I was like "???" when he said, "Yes, when you want to know whether a number is divisible by three, you just add the digits and stuff. Why is that true ? It's magical". I then replied that once we sit down for a coffee I would explain, but then we didn't get a chance to sit down, so I am writing this before sending the url to the weblog entry to him...

So now, as I have just discovered, not everybody knows that result. So let me explain. Take the number 274017. If you want to know whether it is divisible by 3 or not, just add the digits 2+7+4+0+1+7 and doing so you should get 21 which is divisible by 3. Actually, if the fact that 21 is divisible by 3 wasn't obvious to you, you could just apply the method to 21 itself to get 2+1 = 3. Since 3 is divisible by 3, then 21 is divisible by 3 and then 274017 is also divisible by 3. On the other hand, the number 103 is not divisible by 3, since 1+0+3=4.

Now, why does it work. This is where being a mathematician comes in. To transform something that looks like "magical", into something that is not. This said, as for everything interesting, it is not totally trivial, and my main interest in writing this is to check whether or not I can make it simple enough to understand without any mathematical background whatsoever.

**Warning**: The rest of this entry has some maths in it, but really, you don't have to be a math geek to understand. Just pay attention, and read the same sentence twice (or three times), if you don't get it the first time.

I will now introduce a notation. Given a number n, I will denote by [n], the remainder of the division of n by 3. (You should probably read that sentence again until you get it right). For instance, considering n=17, if you divide 17, by 3, then 17 is the **dividend**, 3 is the **divisor**, and we get a **quotient** equal to 5 and a **remainder** equal to 2, leading us to write that 17 = 5 * 3 + 2, but also that [17] = 2. Another example is taking n=27, we have 27 = 9 * 3 + 0, so then [27] = 0.

Now, the reader is invited to notice that, a number n is divisible by 3 if and only if, the rest of the division of n by 3 is zero. Then, using our notation, we have the amazing following fact: a number n is divisible by 3, if and only if [n]=0.

Now, I need to introduce a bit of algebra. Given two numbers n and m, we have [n+m] = [ [n]+[m] ]. Let us look at an example. Take n=5 and m=14. The left hand side of the equality is [5+14] which is equal to [19], itself equal to 1. The right hand side is [ [5]+[14] ], which is [ 2 + 2 ] (I have used that [5] is 2 and that [14] is also 2), which is [4], itself equal to 1. So, we have checked that the equality [n+m] = [ [n]+[m] ] is true when n=5 and m=14. I ask the reader to believe me when I say that it works for any choice of numbers.

Another piece of algebra we need is the following fact: [n * m] = [ [n] * [m] ]. It is the same as before but we replaced the addition by a multiplication. For instance, with the same n=5 and m=14, we have that the left hand side of the last equality is [5 * 14] witch is equal to [70], itself equal to 1. The right hand side is [ [5] * [14] ], which is [ 2 * 2 ], which is [4], itself equal to 1. So, we have checked that the equality [n*m] = [ [n]*[m] ] is true when n=5 and m=14. I ask the ready to believe me when I say that it works all the time.

(**nb**: If you have a mathematical education, you will notice that in the two previous paragraphs, I was simply explaining that the projection of numbers to the **remainder** of their divisions by a positive integer is a ring homomorphism.)

Now, we are ready to move to the main thing. But before the general case I want to emphasis something. Take the number 274017 (the one we started with). We know that this number is divisible by 3 if and only if, [274017]=0. But notice that 274017 = 2*100000 + 7*10000 + 4* 1000 + 0*100 + 1*10 + 7 , so then we have [274017] = [2*100000 + 7*10000 + 4*1000 + 0*100 + 1*10 + 7] = [ [2*100000] + [7*10000] + [4*1000] + [0*100] + [1*10] + [7] ] = [ [2]*[100000] + [7]*[10000] + [4]*[1000] + [0]*[100] + [1]*[10] + [7] ]. (Note that we have used here, the two algebraic equalities that I introduced in previous paragraphs)

At this point, notice that powers of 10, for instance, 10, 100, 1000, 10000, etc, are all such that [power of ten] = 1. (This is easy to see and I should probably prove it carefully, but I am too lazy right now, well, actually it's not laziness, I just want to keep the entry as short as possible).

So then we carry on with: [ [2]*[100000] + [7]*[10000] + [4]*[1000] + [0]*[100] + [1]*[10] + [7] ] = [ [2]*1 + [7]*1 + [4]*1 + [0]*1 + [1]*1 + [7] ] = [ [2] + [7]+ [4] + [0] + [1] + [7] ] = [ 2 + 7+ 4 + 0 + 1 + 7 ] . Therefore, we have that [274017]=0 if and only if [ 2 + 7+ 4 + 0 + 1 + 7 ]=0. In other words, 274017 is divisible by 3, if and only if 2+7+4+0+1+7 is divisible by 3; which is pretty much what we wanted to show.

The last step now, would be to take any number, write it as linear combination of powers of ten, and do the same things as what we just did with 274017. It's easy, and works :-)