Representaciones en base $b$

¿Qué es una base?

La base 10 es familiar, pero no es especial. Cualquier entero $b \ge 2$ puede usarse como base para representar números. En base $b$, cada entero positivo $n$ se escribe de forma única como:

$n = d_k b^k + d_{k-1} b^{k-1} + \cdots + d_1 b + d_0$

donde $0 \le d_i \le b-1$ para todo $i$ y $d_k \ne 0$. Los "dígitos" en base $b$ son los enteros $0, 1, \ldots, b-1$. En base 2 (binaria) solo hay los dígitos $0$ y $1$; en base 16 (hexadecimal) se usan las letras A–F para los "dígitos" 10–15.

La notación $\overline{d_k d_{k-1} \cdots d_0}_{(b)}$ indica que los dígitos se leen en base $b$. Cuando la base es 10 (la usual), se omite el subíndice.

Conversión entre bases

Para convertir $n$ de base 10 a base $b$, se usa la división sucesiva: dividir $n$ por $b$, anotar el resto (que es $d_0$), dividir el cociente por $b$, anotar el resto (que es $d_1$), y así sucesivamente hasta que el cociente sea $0$.

Ejemplo: convertir $45$ a base $3$. $45 = 15 \cdot 3 + 0$; $15 = 5 \cdot 3 + 0$; $5 = 1 \cdot 3 + 2$; $1 = 0 \cdot 3 + 1$. Los restos de abajo hacia arriba dan $45 = \overline{1200}_{(3)}$. Verificación: $1 \cdot 27 + 2 \cdot 9 + 0 \cdot 3 + 0 = 27 + 18 = 45$.

Para convertir de base $b$ a base 10, basta evaluar la expresión polinómica: $\overline{d_k \cdots d_0}_{(b)} = d_k b^k + \cdots + d_0$.

Conversión entre bases distintas de 10: lo más seguro es pasar primero por base 10 como intermediario.

Congruencias en base $b$: el análogo del criterio del 9

Al igual que en base 10 usamos $10 \equiv 1 \pmod 9$, en base $b$ tenemos $b \equiv 1 \pmod{b-1}$. Por lo tanto $b^j \equiv 1 \pmod{b-1}$ y:

$n = d_k b^k + \cdots + d_0 \equiv d_k + d_{k-1} + \cdots + d_0 \pmod{b-1}$.

Es decir, en base $b$, la suma de dígitos da la congruencia módulo $b-1$. Esto generaliza el criterio del 9 (que usa base 10 y módulo 9).

Análogamente, $b \equiv -1 \pmod{b+1}$, así que $n \equiv d_0 - d_1 + d_2 - \cdots \pmod{b+1}$. Esto generaliza el criterio del 11.

Ejemplo: en base 7, ¿es $\overline{3254}_{(7)}$ divisible por 6? La suma de dígitos es $3 + 2 + 5 + 4 = 14 = 2 \cdot 7$, y $14 \equiv 2 \pmod 6$. Entonces $\overline{3254}_{(7)} \equiv 2 \pmod 6$, luego no es divisible por 6.

Problemas olímpicos frecuentes con bases

Tipo 1: "Halla todos los enteros positivos $n$ cuya representación en base 3 tiene exactamente 4 dígitos y cuya representación en base 9 tiene exactamente 2 dígitos." Los números de 4 dígitos en base 3 van de $\overline{1000}_{(3)} = 27$ a $\overline{2222}_{(3)} = 80$. Los de 2 dígitos en base 9 van de $\overline{10}_{(9)} = 9$ a $\overline{88}_{(9)} = 80$. La intersección es $[27, 80]$. Todos los enteros de 27 a 80 satisfacen ambas condiciones.

Tipo 2: "¿En qué bases $b \ge 2$ el número $\overline{121}_{(b)} = b^2 + 2b + 1 = (b+1)^2$ es un cuadrado perfecto?" La respuesta es: para todo $b \ge 2$, pues $(b+1)^2$ siempre es un cuadrado. Este tipo de problema enseña que la representación en base $b$ de ciertos números tiene estructura algebraica elegante.

Tipo 3: condiciones con dígitos repetidos o patrones. Por ejemplo, $\overline{aaa}_{(b)} = a(b^2 + b + 1)$. Si queremos que sea un cuadrado perfecto, necesitamos que $a(b^2 + b + 1)$ sea cuadrado, lo que impone condiciones sobre $a$ y $b^2+b+1$.

Representación en base 2: la más usada en demostraciones

La base binaria (base 2) tiene propiedades especiales por ser la base más pequeña. Todo número se escribe en forma única como suma de potencias distintas de 2: $n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_r}$ con $a_1 > a_2 > \cdots > a_r \ge 0$.

En problemas de olimpiadas, la representación binaria aparece en contextos de: (a) problemas de "juego de Nim" y teoría de juegos, (b) problemas que involucran $\lfloor n/2^k \rfloor$ o la función de Legendre para $v_2(n!)$, (c) condiciones de la forma "la suma de dígitos binarios de $n$ es par" (que equivale a que el número de unos en la representación binaria es par, relacionado con la función de Thue-Morse).

La suma de dígitos binarios, a menudo denotada $s_2(n)$, satisface $s_2(n) \equiv n \pmod 1$... trivialmente. Lo que importa es: $s_2(n)$ cuenta las potencias de 2 en la factorización de $n!$ mediante la fórmula de Legendre: $v_2(n!) = n - s_2(n)$.