Rule of threes, twisted proof
05 Nov 2019For this post, I want to explore a property of the natural numbers (or integers in this case) that is taught at a very young age and whose proof relies on a weird quirk of the decimal system.
Table of contents
The rule of threes
Assume that we have a very large number, like \(543\), and we want to know whether this number is divisible by 3, that is, than when we divide it by three, the remainder is 0:
\[543 = 3\cdot k,\qquad\text{for some }k\in\mathbb{Z}\]An easy way of checking would be to just divide it and see, but, what if that was a lot harder? The rule of threes could help, it tells us that: a number is divisible by three if and only if the sum of its decimal digits is divisible by three. So we check:
\[5+4+3 = 12\]Which is divisible by three! (We could keep going as \(1+2=3\))
With nine the same rule applies, but why does it work?
First, let us get some Mathematics out of the way:
Definitions
In algebra, we call a set with a sum and a multiplication a Ring if those operations have certain properties, we won’t go into a lot of detail, but the basic properties are (we will assume that we are in a commutative ring to ease some complication, this means that \(a\cdot b = b\cdot a\)), let \(R\) be a ring:
- \(R\) is closed by addition, this means that, if we have two elements in \(R\), then their sum will also be in \(R\). Addition also has the following properties:
- It is associative: \(a + (b+c) = (a+b) + c\)
- It is commutative: \(a + b = b + a\)
- There is an element called zero (0) which acts as an identity for the sum, that is \(0+a=a\)
- For every element \(a\) in \(R\) there is an additive inverse called \(-a\), such that \(a + (-a) = 0\).
- \(R\) is closed by multiplication, this means that, if we have two elements in \(R\), then their product will also be in \(R\). Multiplication also has the following properties:
- Commutative. As we stated in the definition, this is not part of the usual definition of ring, but, because we do not1 want to deal with non-commutative rings right now, we will assume that the product is commutative.
- It is associative: \(a\cdot (b\cdot c) = (a\cdot b)\cdot c\)
- There is an element called one (1) which acts as an identity for the multiplication, that is \(1\cdot a = a\)
- Both are associative: \(a(b + c) = ab + ac\)
You might think “Hang on, every set of numbers I know follows this!”2, you are right for the most part. This is why we use this in Algebra.
Say, we have the set of all the integers, usually written as \(\mathbb{Z}\), this is:
\[\mathbb{Z}= \lbrace \cdots, -4,-3,-2,-1, 0, 1,2,3,4,\cdots \rbrace\]what if we wanted to multiply all the elements by, say, three? We wolud write that as:
\[3\mathbb{Z} = \lbrace \cdots, -12,-9,-6,-3, 0, 3,6,9,12,\cdots \rbrace\]And now, what if we want to get only the possible remainders of dividing by three? This is what is called a modular ring, it is defined via a relation we will see in a sec, for now:
\[\mathbb{Z}_3 = \mathbb{Z}/{3\mathbb{Z}} = \lbrace \bar{0}, \bar{1}, \bar{2} \rbrace\]The bar notation will come in handy in a second.
It is clear that the only possible remainders when dividing by three are 0, 1 and 2. We determine which one is the remainder of a number using Euclid’s Algorithm for division, also called Long Division, which gives us, for any integer \(m\):
\[m = 3\cdot k + r\]Where \(k\) is the number we find through division, and \(r\) our remainder. The ring above, what it does, is “squash” every element in \(\mathbb{Z}\) into its modular class, or, the remainder they give out when dividing by three, usually written with the bar, then \(\bar{2}\) would represent any number that gives a remainder of two when dividing by three.
This is what is called a “cyclic” ring, because it is clear that when you add \(\bar{2}+\bar{1}=\bar{0}\), why? Because adding up numbers with a modulo of 2 (remainder of two) and numbers with a modulo of 1 always will give out a multiple of three.
This ring is closed and it has many more nice properties (because 3 is prime) but, why is this so interesting? Because we have a way to embed our numbers here, this is called the modulo operation and it has a very cumbersome notation:
We will say that \(x \equiv 2 \mod 3\) or \(x\equiv \bar{2}\)3 if the remainder when dividing by 3 is 2. This operation, as it is defined, has the nice property of being able to be taken through parentheses, as we saw, due to the cyclical nature of \(\mathbb{Z}_3\), this means, and bear with the horrendous notation:
\[(a+b)\mod 3 = \left[ a \mod 3 + b \mod 3 \right]\mod 3\]Which is the reason I prefer using the bars and pretending that everything is happening inside of a modular ring.
Now, back to the rule of threes:
A proof of the rule of threes
Imagine we are given a number \(x\) in \(\mathbb{Z}\), this number will have a set of digits in decimal, we will refer to these digits as \(x_n,\dots,x_2,x_1,x_0\) such that:
\[x = x_n10^n + \cdots + x_1 10 + x_010^0\](remember that \(10^0 = 0\))
Now, we want to prove that, if \(x\) is divisible by 3, that is, if \(x\equiv 0\mod 3\) or \(x\equiv\bar{0}\), the sum of all its digits is as well.
We begin by taking the modulo of \(x\), we will assume \(x\) is divisible by three to prove the statement:
\[\begin{eqnarray} x \equiv 0\mod 3 \Rightarrow x \mod 3\equiv 0 \Rightarrow (x_n10^n + \cdots + x_1 10 + x_010^0) \mod 3 &\equiv& 0 \\ (x_n10^n\mod 3) + \cdots + (x_1 10\mod 3) + (x_010^0\mod 3) &\equiv& 0 \end{eqnarray}\]Now, we can also take the modulo through the products, and, we will do a change of notation and move to \(\mathbb{Z}_3\), here, because it is a ring:
\[\overline{x_n10^n}=\overline{x_n}\cdot\overline{10^n}\]Now, we rewrite the equation above:
\[\overline{x_n}\cdot\overline{10^n} + \cdots + \overline{x_1}\cdot\overline{10^1} + \overline{x_0}\cdot\overline{1} \equiv \bar{0}\]Now, it is very easy to see that all the powers of ten will be equivalent to 1 modulo 3:
\[\begin{eqnarray} 10 = 3\cdot 3 + 1\therefore \overline{10}&\equiv&\bar{1}\\ \overline{10^2} = \overline{10}\cdot\overline{10}&\equiv& \bar{1}\cdot\bar{1}=\bar{1}\\ \overline{10^3} = \overline{10}\cdot\overline{10^2}&\equiv& \bar{1}\cdot\bar{1}=\bar{1}\\ &\vdots&\\ \overline{10^n} = \overline{10}\cdot\overline{10^{n-1}}&\equiv& \bar{1}\cdot\bar{1}=\bar{1}\\ \end{eqnarray}\]Now, we can rewrite the equation above yet again:
\[\overline{x_n}\cdot\overline{1} + \cdots + \overline{x_1}\cdot\overline{1} + \overline{x_0}\cdot\overline{1} \equiv \bar{0}\]And, because of the asociative property, we will have:
\[(\overline{x_n} + \cdots + \overline{x_1} + \overline{x_0})\overline{1} \equiv \bar{0}\]And now, we have two things, and their product is 0, because \(\mathbb{Z}_3\) behaves properly (read: does not have zero divisors), we will have to assume that, either \((\overline{x_n}\cdot+ \cdots + \overline{x_1}\cdot + \overline{x_0}\cdot)\equiv 0\) or \(\bar{1}\equiv\bar{0}\) and the second one is impossible, so we have that:
\[(\overline{x_n}+ \cdots + \overline{x_1} + \overline{x_0})\equiv 0\]Which means that the sum of the digits is divisible by three
\[\hspace{25cm}\blacksquare\]