Introducción

En las entradas anteriores de teoría de números hemos hablado acerca de divisibilidad, de aritmética modular y de factorización única en primos. En esta entrada vamos a hablar de propiedades que podemos deducir de ciertos números a partir de su dígitos.

Usualmente escribimos a los números en base $10$, usando los dígitos de $1$ a $9$. En realidad, esto es relativamente arbitrario. Podemos usar bases distintas de $10$ para expresar cualquier número de manera (casi) única. Conocer la expresión de un número en cierta base nos permite deducir propiedades algebraicas y de divisibilidad que nos ayuden a resolver problemas.

Expresión en una base arbitraria

Para cualquier base entera $b\ge 2$ que elijamos, cualquier número real se puede expresar de manera (casi) única en base $b$. La afirmación precisa es el siguiente resultado.

Teorema. Sea $r$ un número real y $b\ge 2$ un entero. Entonces, existen únicos enteros $A_0,A_1,\dots ,a_1,a_2,\dots$ en $\{0,1,\dots ,b-1\}$ tales que $$r=\sum _{i=0}^{\mathrm{\infty }}{A}_i{b}^i+\sum _{i=0}^{\mathrm{\infty }}{a}_i{10}^{-i}$$ y $a_i\ne b-1$ para una infinidad de $i$’s.

Para estos $a_i$ y $A_i$ escribimos $$r=(\dots A_2{A}_1{A}_0.a_1{a}_2\dots {)}_b,$$ en donde el subíndice indica la base que se está usando.

La condición de $a_i\ne b-1$ para una infinidad de $i^{\prime }s$ está ahí para garantizar que la expresión sea única pues, por ejemplo, $1=\sum _{i=0}^{\mathrm{\infty }}9\cdot {10}^{-i}=0.9999\dots$, pero esa condición descarta la expresión de la derecha.

Si $b=2$, a esta expresión le llamamos la expresión binaria de $r$.

Ejemplo. La expresión binaria de $4/3$ es $(1.010101\dots {)}_2$. ¿Por qué?

Multiplicar y dividir entre $10$ cuando tenemos números en base $10$ es sencillo: simplemente recorremos el punto decimal. Lo mismo sucede en cualquier base $b$.

Proposición. Cuando tenemos un número en base $b$ y multiplicamos por $b$, el «punto decimal» se recorre a la derecha. Cuando dividimos entre $b$ se recorre a la izquierda.

Problema. Determina si existe un real $x$ tal que $$\lfloor x\rfloor +\lfloor 2x\rfloor +\lfloor 4x\rfloor +\lfloor 8x\rfloor =2222.$$

Sugerencia pre-solución. Trabaja hacia atrás suponiendo que la ecuación sí tiene una solución para determinar cómo tiene que verse $x$. Usa la expresión binaria de $x$.

Solución. Tenemos que $r\ge \lfloor r\rfloor$ para todo real $r$, de modo que si dicho número $x$ existe, se cumple $$17x\ge \lfloor x\rfloor +\lfloor 2x\rfloor +\lfloor 4x\rfloor +\lfloor 8x\rfloor =2222.$$ De aquí, $x\ge 2222/17=130.705\dots \ge 130$. También, $r\le \lfloor r\rfloor +1$, de modo que si $x$ existe necesitamos $$17x\le \lfloor x\rfloor +\lfloor 2x\rfloor +\lfloor 4x\rfloor +\lfloor 8x\rfloor +4=2226.$$

De aquí, $x\le 2226/17=130.94\le 131$.

Esto nos dice que $x$ es un real entre $130$ y $131$. Escribámoslo como $130$ más una parte fraccional en base $2$, es decir, de la forma $x=130+(abcde\dots {)}_2$. Multiplicar por $2$ simplemente recorre el punto decimal en base $2$ un lugar hacia la derecha, de modo que
$$\begin{array}{rl}2x& =260+(a.bcde\dots {)}_2\\ 4x& =520+(ab.cde\dots {)}_2\\ 8x& =1040+(abc.de\dots {)}_2,\end{array}$$ y por lo tanto
$$\begin{array}{rl}\lfloor x\rfloor & =130\\ \lfloor 2x\rfloor & =260+(a{)}_2=260+a\\ \lfloor 4x\rfloor & =520+(ab{)}_2=520+2a+b\\ \lfloor 8x\rfloor & =1040+(abc{)}_2=1040+4a+2b+c.\end{array}$$

Concluimos entonces que la suma buscada es igual a $1950+7a+3b+c$. Si existe el número que queremos, la ecuación $$1950+7a+3b+c=2222$$ debe tener una solución con $a$, $b$ y $c$ iguales a $0$ o a $1$. Pero esto es imposible, pues incluso aunque los tres sean iguales a $1$, tenemos a lo más $1950+11=1961$. De esta forma, no existe la $x$ que buscamos.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Bases y números racionales

Una sucesión infinita $\{a_1,a_2,\dots ,\}$ es preperiódica si existen enteros positivos $n$ y $d$ tales que $a_m=a_{m+d}$ para todo entero $m\ge n$. A $d$ se le llama un periodo de la sucesión, y decimos que $\{a_1,a_2,\dots \}$ es periódica a partir de $a_n$.

Teorema. Sea $r$ un número real. Las siguientes tres afirmaciones son equivalentes:

• $r$ es racional.
• Para toda base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\dots \}$ es preperiódica.
• Para alguna base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\dots \}$ es preperiódica.

Problema. Considera el número en binario $$r=(0.a_1{a}_2{a}_3\dots {)}_2$$ en donde $a_i=0$ si $i$ es primo y $a_i=1$ si no. Determina si $r$ es un número racional o irracional.

Sugerencia pre-solución. Procede por contradicción, suponiendo que $r$ es racional.

Solución. Si $r$ fuera racional, la sucesión $\{a_1,a_2,\dots \}$ sería preperiódica, de modo que existirían $n$ y $d$ tales que $a_{m+d}=a_m$ para todo $m\ge n$. Consideremos el bloque de $d$ dígitos $(a_n{a}_{n+1}\dots a_{n+d-1}{)}_2$. Como el periodo de la sucesión es $d$, a partir de $a_n$ este bloque de dígitos se repite.

Los números

$$\begin{array}{rl}M& =n(2d+1)!+2,\\ M+1& =n(2d+1)!+3,\\ & ⋮\\ M+(2d-1)& =n(2d+1)!+(2d+1)\end{array}$$

son $2d$ números consecutivos mayores a $n$ y tales que ninguno de ellos es primo, pues el primero es divisible entre $2$, el segundo entre $3$, …, y el último entre $2d+1$. Esto muestra que el bloque de $d$ dígitos debe consistir de puros $1$’s, pues uno de los bloques del ciclo queda contenido en el bloque de $2d$ dígitos $(a_M{a}_{M+1}\dots a_{M+2d-1}{)}_2$. Así, a partir de $a_n$ todos los dígitos son iguales a $1$.

Pero esto es imposible, pues quiere decir que todos los enteros mayores o iguales a $n$ no son primos. Esto contradice que hay una infinidad de números primos.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Criterios de divisibilidad

Si sabemos cómo es la expresión de un número en una base, entonces a veces podemos decir cosas acerca de su divisibilidad o residuo al dividirse entre algunos enteros relacionados con la base. Cuando estamos trabajando módulo $10$ tenemos el siguiente resultado.

Proposición (criterios de divisibilidad base 10). Sea $n$ un entero positivo. En base $10$,

• $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo ${10}^k$, y por lo tanto también módulo $2^k$ y módulo $5^k$.
• $n$ es congruente con la suma de sus dígitos módulo $9$, y por lo tanto también módulo $3$.
• Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo ${10}^j+1$.

Demostrar estos criterios es sencillo. Por ejemplo, un número $(A_n{A}_{n-1}\dots A_0{)}_{10}$ en base $10$ es igual a $${10}^n{A}_n+{10}^{n-1}{A}_{n-1}+\dots +10A_1+A_0.$$ Trabajando módulo $9$, todos los $10$ son $1$, así que $$n={10}^n{A}_n+\dots +A_0\equiv A_n+A_{n-1}+\dots +A_0.$$

Como ejemplo del último criterio, considera el siguiente problema:

Problema. ¿Cuál es el residuo que queda al dividir $n=1512513514515$ entre $13$?

Sugerencia pre-solución. Usa el tercer criterio de divisibilidad base $10$ para $j=3$. Factoriza $1001$.

Solución. Vamos a estudiar al número módulo $1001$. Para esto, agrupamos los dígitos de tres en tres, de derecha a izquierda $$515,514,513,512,1$$ y hacemos la suma alternada $$515-514+513-512+1=3.$$ Por el tercer criterio de divisibilidad, tenemos que $n\equiv 3(\mathrm{mod}1001)$. Notemos que $1001=7\cdot 11\cdot 13$, de modo que $n\equiv 3(\mathrm{mod}13)$. Así, el residuo al dividir $n$ entre $13$ es $3$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

En general, tenemos lo siguiente.

Proposición (criterios de divisibilidad base $b$). Sea $n$ un entero positivo. En base $b$:

• $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo $b^k$, y por lo tanto también módulo $d^k$ para cualquier divisor $d$ de $b$.
• $n$ es congruente con la suma de sus dígitos módulo $b-1$ (y por lo tanto también módulo cualquier divisor de $b-1$)
• Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo $b^j+1$.

Problema. Considera los números del $1$ al $500$ (inclusive). ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en base $3$? ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en binario?

Sugerencia pre-solución. Haz casos pequeños para encontrar un patrón que te diga cuántos números del $1$ al $n$ tienen una cantidad impar de $1$’s en su expresión en base $2$ y $3$. Para demostrar el resultado para base $3$, usa criterios de divisibilidad generalizados. Para base $2$ usa paridad y aprovecha la simetría.

Solución. Un número en base $3$ es congruente con la suma de sus dígitos módulo $2$. En base $3$ el único dígito impar es el $1$. Así, un número en base $3$ es congruente a su cantidad de dígitos $1$ módulo $2$. De esta forma, $n$ tiene una cantidad impar de $1$’s si y sólo si es impar. Por lo tanto, hay $250$ números entre $1$ y $500$ que tienen una cantidad impar de $1$’s en su expresión en base $3$.

En base $1$ el patrón no es tan claro. Los primeros números son $1$, $10$, $11$, $100$, $101$, $110$, $111$. A veces cuando se cambia de cantidad de dígitos se cambia la paridad de $1$’s (como de $11$ a $100$) y a veces no (como de $111$ a $1000$). Haremos entonces un argumento de emparejamiento.

Notemos que cualquier número par $2n$ termina en $0$ en binario y que $2n+1$ tiene la misma expansión salvo el último dígito, que ahora es $1$.Así, a los números del $2$ al $499$ los podemos agrupar en parejas en donde en cada pareja los números tienen distinta paridad de $1$’s. De esta forma, aquí hay $498/2=249$ números con una cantidad impar de $1$’s. El $1$ tiene una cantidad impar de $1$’s. El $500$ en binario es $(111110100{)}_2$, que tiene una cantidad par de $1$’s. Así, hay $250$ números entre $1$ y $500$ con una cantidad impar de $1$’s en binario.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.4 del libro Problem Solving through Problems de Loren Larson.