05 Nov 2019
Leer en Español
For 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 not 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!”, 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}\) 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\]
05 Nov 2019
Read in English
Para esta entrada, me gustaría explorar una propiedad de los numeros naturales (o enteros en este caso) que se enseña en primaria, pero su demostración requiere una pequeña peculiaridad del sistema decimal.
Índice
La regla del tres
Pongamos que tenemos un número grande, como \(543\), y queremos saber si es divisible por tres, es decir, que si cuando lo dividamos entre tres, el resto sea 0
\[543 = 3\cdot k,\qquad\text{para algún }k\in\mathbb{Z}\]
Una manera sencilla de comprobarlo, sería dividir y ya está, pero, ¿y si fuese mucho más difícil? La regla del tres podría asistirnos, dice: un número es divisible entre tres si y sólo si la suma de sus dígitos decimales es divisible entre tres. Así que comprobamos:
\[5+4+3 = 12\]
¡Es divisible entre tres! (De hecho, podríamos seguir dado que \(1+2=3\))
Con el nueve tenemos una regla similar, pero, ¿por qué funciona?
Primero, quitémonos unas pocas definiciones de en medio:
Definiciones
En álgebra, llamamos a un conjunto que tiene definido sobre sus elementos una suma y una multiplicación un anillo, si esas operaciones cumplen ciertas propiedades, no nos metemos en mucho detalle, pero las propiedades básicas son (vamos a asumir que estamos en un anillo conmutativo, esto significa que \(a\cdot b = b\cdot a\)), sea \(R\) un anillo:
- \(R\) esta cerrado por la suma, esto quiere decir que si tenemos dos elementos del anillo y los sumamos, “no nos salimos”, es decir, la suma sigue estando en el anillo. La sima también cumple las siguientes propiedades:
- Es asociativa: \(a + (b+c) = (a+b) + c\)
- Es conmutativa: \(a + b = b + a\)
- Existe un elemento llamado cero (0) que actúa como elemento neutro para la suma, esto quiere decir que \(0+a=a\)
- Para cada elemento \(a\) en \(R\) existe una inversa aditiva llamada \(-a\), tal que \(a + (-a) = 0\).
- \(R\) esta cerrado por la multiplicación, esto quiere decir, como antes, que si multiplicamos dos elementos del anillo, el producto segirá estando en el anillo. El producto también tiene las siguientes propiedades:
- Conmutativo. Como hemos dicho en la definición, esto no forma parte de la definición normal de anillo, pero, como no queremos meternos en anillos no conmutativos, asumiremos que la multiplicación es conmutativa.
- Es asociativa: \(a\cdot (b\cdot c) = (a\cdot b)\cdot c\)
- Existe un elemento llamado uno (1) que actúa como identidad para la multiplicación, es decir \(1\cdot a = a\)
- Ambas son asociativas entre sí: \(a(b + c) = ab + ac\)
Puede que estés pensando “Espera un segundo, ¡todos los conjuntos de números que conozco siguen esta definición!”, estás en lo cierto en su mayor parte, por eso mismo usamos esta definición en álgebra.
Digamos ahora, que tienes el conjunto de todos los enteros
\[\mathbb{Z}=
\lbrace
\cdots, -4,-3,-2,-1,
0,
1,2,3,4,\cdots
\rbrace\]
¿Qué pasaría si quisiésemos multiplicar todos los elementos por, que se yo, tres? Esto se escribiría como sigue:
\[3\mathbb{Z} =
\lbrace
\cdots, -12,-9,-6,-3,
0,
3,6,9,12,\cdots
\rbrace\]
Y ahora, ¿y si queremos todos los posibles restos de dividir entre tres? Esto es lo que llamamos anillos modulares, y se definen con una relación que veremos en un momento, por ahora:
\[\mathbb{Z}_3 = \mathbb{Z}/{3\mathbb{Z}} = \lbrace
\bar{0}, \bar{1}, \bar{2}
\rbrace\]
La notación con la barra vendrá muy bien más adelante.
Está claro que los únicos posibles restos de dividir entre tres son 0, 1 y dos. Determinamos cual es el resto de un número usando el Algoritmo Euclídeo de división, también llamado división con caja, lo cual nos da, para un entero cualquiera \(m\):
\[m = 3\cdot k + r\]
Donde \(k\) es el cociente, y \(r\) nuestro resto. Lo que hace el anillo de arriba es “comprimir” todos los elementos de \(\mathbb{Z}\) en su clase modular, o, el resto que dan al dividir entre tres, en general escrito con la barra, entonces \(\bar{2}\) representará cualquier número que de un resto de 2 cuando dividamos entre tres.
Este anillo es lo que se llama un “anillo cíclico”, porque está claro que si sumamos \(\bar{2}+\bar{1}=\bar{0}\), ¿por qué? Porque sumar un número que de resto 1 y un número que de resto 2 (dividiendo entre tres) siempre dará un número divisible entre tres.
Este anillo está cerrado y tiene buenas propiedades (al ser 3 un número primo) pero, ¿a qué va todo esto? Porque tenemos una manera de incrustar nuestro números en decimal aquí, es el operador módulo, y tiene una notacción horrorosa:
Diremos que \(x \equiv 2 \mod 3\) o \(x\equiv \bar{2}\) si el resto al dividir entre tres es dos. Esta operación, tal y como está definida, tiene la buena propiedad de poder meterla a través de paréntesis como consecuencia de que \(\mathbb{Z}_3\) es un anillo cíclico, Esto significa, y perdón por la notación pero no la he inventado yo, que:
\[(a+b)\mod 3 = \left[
a \mod 3 + b \mod 3
\right]\mod 3\]
Lo cual es la razón por la que prefiero usar las barras y fingir que todo lo que pasa debajo está en un anillo modular.
Volvemos a la regla del tres:
Una demostración de la Regla del Tres
Imaginemos que nos dan un número \(x\) en \(\mathbb{Z}\), este número tendrá una serie de dígitos en decimal, nos referiremos a estos dígitos como \(x_n,\dots,x_2,x_1,x_0\) tal que:
\(x = x_n10^n + \cdots + x_1 10 + x_010^0\)
(recordamos que \(10^0 = 0\))
Ahora, queremos demostrar que, si \(x\) es divisible entre 3, es decir, si \(x\equiv 0\mod 3\) o \(x\equiv\bar{0}\), la suma de sus dígitos también lo es.
Comenzamos tomando el módulo de \(x\), asumiremos que \(x\) es divisible entre tres para así demostrar la afirmación:
\[\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}\]
Ahora, pasamos el módulo dentro de los productos y hacemos un cambio de notación para trasladarnos a \(\mathbb{Z}_3\), aquí, como es un anillo:
\[\overline{x_n10^n}=\overline{x_n}\cdot\overline{10^n}\]
Ahora, podemos reescribir la ecuación de arriba como:
\[\overline{x_n}\cdot\overline{10^n}
+ \cdots +
\overline{x_1}\cdot\overline{10^1} +
\overline{x_0}\cdot\overline{1} \equiv \bar{0}\]
Ahora, es fácil ver que todas las potencias de diez serán equivalentes a 1 mod 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}\]
Ahora, reescribiendo de nuevo la ecuación de arriba:
\[\overline{x_n}\cdot\overline{1}
+ \cdots +
\overline{x_1}\cdot\overline{1} +
\overline{x_0}\cdot\overline{1} \equiv \bar{0}\]
Y, usando la propiedad asociativa:
\[(\overline{x_n}
+ \cdots +
\overline{x_1} +
\overline{x_0})\overline{1} \equiv \bar{0}\]
Y ahora, tenemos dos cosas, y su producto es cero, como \(\mathbb{Z}_3\) se porta bien (véase: no tiene divisores del cero), tendremos que asumir que, o bien \((\overline{x_n}\cdot+ \cdots + \overline{x_1}\cdot + \overline{x_0}\cdot)\equiv 0\) o \(\bar{1}\equiv\bar{0}\) y lo segundo es imposible, así que tendremos:
\[(\overline{x_n}+ \cdots + \overline{x_1} + \overline{x_0})\equiv 0\]
Lo que significará que la suma de los dígitos es divisible entre tres.
\[\hspace{25cm}\blacksquare\]
