To divide or not to divide by 3?
Both teams had to decide, from a list of numbers, which ones were divisible by $3$. Now, there are a few ways to test that. The obvious one is just to divide the number by $3$ and see if it works, but that wasn’t what the quizmasters were looking for. They wanted an insight such that you can see it quicker. The teams had to bid on how many correct answers they could give. The team that bid the highest number of answers got to play but if they got one wrong, the other team would steal the points obtained by the other team.
By pure coincidence, I actually knew someone on one of the teams. Obviously I was rooting for my friend’s team and the main reason why I kept watching in the first place. His team got the opportunity to answer which numbers from the list were divisible by $3$. The exact list of numbers was: $$ 1\,424, \, 622, \, 99, \, 358\,442, \, 100 \,002, \, 1 \,798,\, 99 \,345, \, 5 \,565 $$ Then suddenly one of the team members of my friend’s team said “$100$ $002$ is not divisible by $3$” and my humble judgement of the situation was:
“NOOOOOOOOOOO, THAT IS WRONGGGGGG.”
Maybe a bit dramatic, but indeed he was wrong, but why was he wrong?
Well, it can be a treacherous question and I don’t want to rag on the person giving the wrong answer. In a high pressure environment, like a quiz on national television, it is easier to make mistakes like these. Unfortunately, this mistake cost my friend’s team the game, but they put up a hell of a fight. It was a great game to watch. However, it made me realize that it would be a good blog post because it might not be directly evident why $100$ $002$ is divisible by $3$?
A first idea of determining divisibility
Let’s start with defining what divisibility by $3$ actually means. If a $\text{number} $ is divisible by $3$, it means we can write it as: $$ \text{number} = 3 \times n $$ for some whole number $n$.Now, here’s something simple but powerful. If a number is divisible by $3$, then subtracting, or adding, any multiple of $3$ keeps it divisible by $3$. For example, $$ 100002 - 3 = 99999 $$ since $99999 = 3 \times 33333$, both $99\,999$ and $100$ $002$ must be divisible by $3$.
Some Examples
So the basic idea is that subtraction doesn’t break divisibility as long as you subtract a multiple of $3$. What about the other numbers?Example 1
Wel, $99$ is easy because it is obviously divisible by $3$.Example 2
For $1$ $424$ we can subtract $24$, which is divisible by $3$, and then obtain 1400 which is not divisible by $3$ as it can only be divided by $2,7$ and $10$.Example 3
The number $622$ can be subtracted by $600$, which is divisible by $3$, to obtain $22$ which is only divisible by $2$ and $11$.Example 4
For $358$ $442$, we need to do some more work: $$ 358 442 – 3\cdot 110 000 = 28 442 $$ $$ 28 442 - 27 000 = 1442 $$ $$ 1442 – 42 = 1400 $$ As said before, $1\,400$ is not divisible by $3$.Example 5
Then $1$ $798$ can be $$ 1798 – 1500 = 298 $$ $$ 298 – 270 = 28 = 4\cdot7 $$ So 1798 is not divisible by $3$.Example 6
You can see that $99$ $345$ is divisible by $3$ because $$ 99 345 – 9\cdot11 000 = 345 $$ $$ 345 – 300 = 45 $$ $$ 45 = 3\cdot3\cdot5 = 9\cdot5 $$ Hence, 99 345 is divisible by 3.Example 7
And last but not least $5$ $565$: $$ 5 565 – 5400 = 165 $$ $$ 165 – 150 = 15 $$ $$15 = 3\cdot5 $$ Hence, $5$ $565$ is divisible by $3$. So in essence, this is a small trick to see whether a number is divisible by another number. This is how I determined that $100\,002$ was divisible by $3$. BUUUUUUT, we are not done yet. What if I told you we can have an even easier way to see if a number is divisible by $3$? To make this question more evident, we need to use some modular arithmetic.Determining divisibility using modular arithmetic
In the world of mathematics and cryptography, modular arithmetic plays a crucial role, especially in understanding security algorithms that protect our sensitive information. Two natural numbers $a$ and $b$ that are congruent modulo with respect to a natural number $m>1$ if:$a-b$ is a multiple of $m$, formally written as $a≡b \mod m$. The number $m$ is called the modulus. The triple parentheses in the expression indicate that mod m applies to the entire equation, not just the right-hand side. Let's explore this fascinating branch of mathematics and discover why it's so relevant.
Consider numbers that exhibit cyclical behaviour, like the hours on a clock. Modular arithmetic is the mathematical language we use to understand these cycles. For example, if we say it's $9$ p.m. and we add $4$ hours, we arrive at $1$ a.m. This is modular arithmetic in action. We have $24$ hours in a day. Do we have $24$ digits representing $24$ hours on a clock? Usually not (some do however), but we can still understand $24$-hour times with just $12$ digits. What we're actually doing is a modulus $12$ operation. We're wrapping around every urs.
Another example is imagining a circle with a circumference of 10 units and a wire $35$ units long. Wrapping this wire around the circle reflects the concept of modulus. After one complete revolution, $25$ units of wire remain, illustrating the concept of congruence. $35$ is congruent to $25 \mod 10$, symbolizing a valid congruence. If we perform a second wrap, the remaining wire is reduced to $15$ units. The congruence now transforms to $35$, congruent to $15 \mod 10$. A third wrap results in only $5$ length units of the wire left.
Ok, very nice, one would say, but why care? This modulo arithmetic is actually quite interesting because we can use the following aspects. $$ ab \, \mod m = a \, \mod m \, b \, \mod m $$ $$ a + b \, \mod m = \left( a \, \mod m + b \, \mod m \right) \, \mod m $$ So you know that a number can be written in a decimal expansion: $$ N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_1 10 + d_0$$ Where $d_0,d_1,\cdots , d_k$ are the digits of the number. So what happens when we take the modulo of this number? Then by using the earlier formulas we can just say that: $$ N \mod 3 = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_1\cdot 10 + d_0 \mod 3$$ $$ N \mod 3 = d_k 1^k + d_{k-1} 1^{k-1} + \cdots + d_1 \cdot 1 + d_0 \mod 3$$ $$ N \mod 3 = d_k + d_{k-1} + \cdots + d_1 + d_0 \mod 3$$ Crazy right? If this is not evident, try to see for yourself why this is the case. So in essence, the remainder of a number when divided by $3$ is the same as the remainder of the sum of its digits when divided by $3$.
So if the sum of a number’s digits is divisible by $3$, the number itself must also be divisible by $3$. Let’s check with our earlier example of $100\, 002$ if this really makes sense: $$ 1 + 0 + 0 + 0+ 0 + 2 = 3$$ As $3$ is obviously divisible by $3$ itself, the original number $100\, 002$ is divisible as well. I have to be honest that I was unaware of this trick before this gameshow. So for me it was a nice discovery of how easily you can see whether a number is divisible by $3$.
So if a number looks messy, just keep subtracting an easy multiple of $3$ until you get something recognizable. Or even better, add the digits. It’s in essence, the same idea dressed up in a simpler form.
It’s a nice party trick to show your friends or maybe it can win your team some points in a quiz.
Comments
Post a Comment