1.6: La Base b Representación de n

En este capítulo mostramos cómo el Algoritmo de División se relaciona con un concepto tocado desde las matemáticas de primaria.

Definición\(\PageIndex{1}\): Decimal Representation

Recordemos que la representación decimal de un entero positivo\(a\) viene dada por\(a =a_{n-1}a_{n-2}\cdots a_1a_0\) donde\[\label{decimalrep} a = a_{n-1}10^{n-1} + a_{n-2}10^{n-2} + \cdots + a_110 + a_0\] y los dígitos\(a_{n-1},a_{n-2},\dots,a_1,a_0\) están en el conjunto\(\{0,1,2,3,4,5,6,7,8,9\}\) con\(a_{n-1}\neq 0\). En este caso decimos que el entero\(a\) es un número\(n\) -dígito o que\(a\) es \(n\)dígitos largos.

Por ejemplo, se entiende que los números en “682” significan seiscientos ochenta y dos, porque las ubicaciones de 6, 8 y 2 (en el “lugar de los cien”, “lugar de diez” y “lugar de uno”) indican el número\(6 \cdot 100 + 8\cdot 10 + 2\).

En este capítulo justificaremos la afirmación de que cada entero positivo tiene una representación decimal. No obstante, lo haremos en un marco más general.

Definición\(\PageIndex{2}\): Base \(b\) Representation of \(n\)

Dejar\(b\ge 2\) y\(n>0\). Escribimos\[\label{eq:base} n=\left[a_k,a_{k-1},\dotsc,a_1,a_0\right]_b\] si y solo si para algunos\(k\ge 0\)\[n=a_kb^k+a_{k-1}b^{k-1}+\dotsb+a_1b+a_0\nonumber \] donde\(a_i\in\{0,1,\dotsc,b-1\}\) para\(i=0,1,\dotsc,k\). \(\left[a_k,a_{k-1},\dotsc,a_1,a_0\right]\)se llama una\(b\) representación base de\(n\).

OBSERVACIÓN\(\PageIndex{1}\)

Base\(b\) se conoce como\[\begin{aligned} binary\quad & \text{if }b=2, \\ ternary\quad & \text{if }b=3, \\ octal\quad & \text{if }b=8, \\ decimal\quad & \text{if }b=10, \\ hexadecimal\quad & \text{if }b=16.\end{aligned}\] Si\(b\) se entiende, especialmente si\(b=10\), escribimos\(a_ka_{k-1}\dotsm a_1a_0\) en lugar de\(\left[a_k,a_{k-1},\dotsc,a_1,a_0\right]_{b}\). En el caso de\(b=16\), que se utiliza frecuentemente en informática, los “dígitos”\(10\),,\(11\),\(12\)\(13\),\(14\) y\(15\) se sustituyen por\(A\), \(B\),\(C\)\(D\),\(E\) y\(F\), respectivamente.

Para una base fija\(b\ge 2\), los números\(a_i\in\{0,1,2,\dotsc,b-1\}\) en la ecuación\(\eqref{eq:base}\) se denominan los dígitos de la\(b\) representación base de\(n\). En el caso binario\(a_i\in\{0,1\}\) y los\(a_i\)'s se llaman bits (bi nary digi ts).

Aquí hay algunos ejemplos:

1. \(267=[5,3,1]_7\)ya que\(267 = 5 \cdot 7^2+3\cdot 7 +1\).
2. \(147=[1,0,0,1,0,0,1,1]_2\)ya que\(147=1\cdot 2^7+0\cdot 2^6+0\cdot 2^5+1\cdot 2^4+0\cdot 2^3+0\cdot 2^2+1\cdot 2+1\).
3. \(4879=[4,8,7,9]_{10}\)ya que\(4879 = 4\cdot 10^3+8\cdot 10^2 + 7\cdot 10 + 9\).
4. \(10705679=[A,3,5,B,0,F]_{16}\)ya que\(10705679=10\cdot 16^5+3\cdot 16^4+5\cdot 16^3+11\cdot 16^2+0\cdot 16+15\).
5. \(107056791=[107, 56, 791]_{1000}\)ya que\(107056791=107\cdot 1000^2+56\cdot 1000 +791\).

Teorema\(\PageIndex{1}\): Base \(b\) Representation

Si\(b\ge 2\), entonces cada uno\(n>0\) tiene una\(b\) representación base única de la forma\(n=\left[a_k,\dotsc,a_1,a_0\right]_b\) con\(a_k>0\).

Prueba

Aplicar repetidamente el Algoritmo de División de la siguiente manera:\[\begin{aligned} n &=bq_0+r_0,\quad 0\le r_0<b \\ q_0 &=bq_1+r_1,\quad 0\le r_1<b \\ q_1 &=bq_2+r_2,\quad 0\le r_2<b \\ &\qquad\vdots \\ q_{k-1} &=bq_k+r_k,\quad 0\le r_k<b \\ q_k &=bq_{k+1}+r_{k+1},\quad 0\le r_{k+1}<b.\end{aligned}\] Tenga en cuenta que en cada paso siempre dividimos por\(b\). En la primera línea, dividimos\(n\) por\(b\), y luego en cada línea después de la primera, lo que dividimos por\(b\) es el cociente de la línea anterior; luego usamos el cociente resultante para la siguiente línea.

De la división repetida no es difícil ver eso mientras\(q_k>0\), es cierto que\[n>q_0>q_1>\dotsm>q_k.\nonumber \] Dado que esto no puede continuar para siempre finalmente obtenemos\(q_\ell=0\) para algunos\(\ell\). Entonces tenemos\[q_{\ell-1}=b\cdot 0+r_\ell.\nonumber \] Afirmamos que\(n=\left[r_\ell,r_{\ell-1},\dotsc,r_0\right]_b\) si\(\ell\) es el entero más pequeño tal que\(q_\ell=0\). Para ver esto, tenga en cuenta que\[n=bq_0+r_0\nonumber \] y\[q_0=bq_1+r_1.\nonumber \] De ahí\[\begin{aligned} n &=b\left(bq_1+r_1\right)+r_0 \\ n &=b^2q_1+br_1+r_0.\end{aligned}\] Continuando de esta manera nos encontramos con eso\[n=b^{\ell+1}q_{\ell}+b^\ell r_\ell+\dotsb+br_1+r_0.\nonumber \] Y, ya\[\label{eq: base b again} n=b^\ell r_\ell+\dotsb+br_1+r_0,\] que\(q_\ell=0\) tenemos lo que demuestra que\[n=\left[r_\ell,\dotsc,r_1,r_0\right]_b.\nonumber \] Para ver que esta representación es única, señalar que a partir de la ecuación\(\eqref{eq: base b again}\) tenemos\[n=b\left(b^{\ell-1}r_\ell+\dotsb+r_1\right)+r_0,\quad 0\le r_0<b.\nonumber \] Por el Algoritmo de División se deduce que\(r_0\) está determinado de manera única por\(n\), como es el cociente\(q=b^{\ell-1}r_\ell+\dotsb+r_1\). Un argumento similar muestra que\(r_1\) está determinado de manera única. Continuando de esta manera vemos que todos los dígitos\(r_\ell,r_{\ell-1},\dotsc,r_0\) están determinados de manera única.

Ejemplo \(\PageIndex{1}\): Base Conversions

Podemos utilizar la idea de la prueba del Teorema\(\PageIndex{1}\), aplicaciones repetidas del Algoritmo de División, para expresar números en una base arbitraria. A continuación se presentan algunos ejemplos.

1. Encontramos la\(7\) representación base de\(1\),\(749\). \[\begin{aligned} 1749 &=249\cdot 7+6 \\ 249 &=35\cdot 7+4 \\ 35 &=5\cdot 7+0 \\ 5 &=0\cdot 7+5\end{aligned}\]De ahí\(1749=[5,0,4,6]_7\).
2. Encontramos la\(12\) representación base de\(19\),\(151\). \[\begin{aligned} 19,151 &=1595\cdot 12+11 \\ 1,595 &=132\cdot 12+11 \\ 132 &=11\cdot 12+0 \\ 11 &=0\cdot 12+11\end{aligned}\]\(\therefore 19,151=[11,0,11,11]_{12}\).
3. Encuentra la\(10\) representación base de\(1\),\(203\). \[\begin{aligned} 1203 &=120\cdot 10+3 \\ 120 &= 12\cdot 10+0 \\ 12 &=1\cdot 10+2 \\ 1 &=0\cdot 10+1\end{aligned}\]\(\therefore 1203=[1,2,0,3]_{10}\).
4. Encuentra la representación base\(2\) (binaria) de\(137\). \[\begin{aligned} 137 &=2\cdot 68+1 \\ 68 &=2\cdot 34+0 \\ 34 &=2\cdot 17+0 \\ 17 &=2\cdot 8+1 \\ 8 &=2\cdot 4+0 \\ 4 &=2\cdot 2+0 \\ 2 &=2\cdot 1+0 \\ 1 &=2\cdot 0+1\end{aligned}\]\(\therefore 137=[1,0,0,0,1,0,0,1]_2\).

OBSERVACIÓN\(\PageIndex{2}\)

Para encontrar la representación binaria de un número pequeño, el siguiente método suele ser más fácil que el método anterior:

Dado\(n>0\) dejó\(2^{n_1}\) ser el mayor poder de\(2\) satisfacción\(2^{n_1}\le n\). Que\(2^{n_2}\) sea el mayor poder de\(2\) satisfacer\[2^{n_2}\le n-2^{n_1}.\nonumber \] Dejemos\(2^{n_3}\) ser el mayor poder de\(2\) satisfacción\[2^{n_3}\le n-2^{n_1}-2^{n_2}.\nonumber \] Tenga en cuenta que en este punto tenemos\[0\le n-\left(2^{n_1}+2^{n_2}+2^{n_3}\right)<n-\left(2^{n_1}+2^{n_2}\right)<n-2^{n_1}<n.\nonumber \] Continuando de esta manera, eventualmente obtenemos\[0=n-\left(2^{n_1}+2^{n_2}+\dotsb+2^{n_k}\right).\nonumber \] Entonces \(n=2^{n_1}+2^{n_2}+\dotsb+2^{n_k}\), y esto da la representación binaria de\(n\).

Ejemplo\(\PageIndex{2}\)

Tomar\(n=137\). Tenga en cuenta que\(2^1=2\)\(2^2=4\),\(2^3=8\),\(2^4=16\),\(2^5=32\),\(2^6=64\),,\(2^7=128\), y\(2^8=256\). Usando el método anterior calculamos:\[\begin{aligned} 137-2^7 &=137-128=9, \\ 9-2^3 &=1, \\ 1-2^0 &=0.\end{aligned}\] Así que tenemos\[\begin{gathered} 137=2^7+9=2^7+2^3+1, \\ \therefore 137=2^7+0\cdot2^6+0\cdot2^5+0\cdot2^4+2^3+0\cdot2^2+0\cdot 2+1.\end{gathered}\] So\(137=[1,0,0,0,1,0,0,1]_2\).

Ejercicios

Ejercicio \(\PageIndex{1}\)

Generaliza las siguientes observaciones\[\begin{aligned} 1 &=[1]_2 \\ 3 &=[1,1]_2 \\ 7 &=[1,1,1]_2 \\ 15 &=[1,1,1,1]_2 \\ 31 &=[1,1,1,1,1]_2 \\ 63 &=[1,1,1,1,1,1]_2\end{aligned}\] notando un patrón en los números en los lados izquierdos y conjeturando una fórmula para el número que tiene\(n\) 1's en su representación binaria. Demuestra tu generalización.

(Pista: Ver Ejercicio 1.3.8.)

Ejercicio \(\PageIndex{2}\)

Generalizar la siguiente observación:\[\begin{aligned} 2 &=[2]_3\\ 8 &=[2,2]_3 \\ 26 &=[2,2,2]_3 \\ 80 &=[2,2,2,2]_3 \\ 242 &=[2,2,2,2,2]_3\end{aligned}\] notando un patrón en los números en los lados izquierdos y conjeturando una fórmula para el número que tiene\(n\) 2's en su representación ternaria. Demuestra tu generalización.

(Pista: Ver Ejercicio 1.3.8.)

Ejercicio\(\PageIndex{3}\)

Generalizar Ejercicios\(\PageIndex{1}\) y \(\PageIndex{2}\)a una base arbitraria\(b\ge 2\).

Ejercicio\(\PageIndex{4}\)

Mostrar cómo usar ambos métodos para encontrar la representación binaria de\(455\).

Ejercicio\(\PageIndex{5}\)

Hacer una lista vertical de la representación binaria de los enteros 1 a 16.

Ejercicio\(\PageIndex{6}\)

Encuentra la representación decimal de cada uno de los siguientes números.

1. \([5,3,6,2]_7\);
2. números hexadecimales FEEDAFACE y BADBEEF.

Ejercicio\(\PageIndex{7}\)

Siguiendo la técnica del Ejemplo\(\PageIndex{1}\), encuentra las representaciones de 12345 en (i) base 3 y (ii) base 8. Para ambas partes (i) y (ii), muestre su trabajo con el mismo nivel de detalle que Ejemplo\(\PageIndex{1}\).

Ejercicio\(\PageIndex{8}\)

Encuentra la representación de base 7 del número\([1,2,3,4,5,6,7,8]_9\).

Ejercicio \(\PageIndex{9}\)

Demostrar que si\(a\in\mathbb{N}\) es un número\(n\) -dígito, entonces\(n={\mbox{\) (a)\(}}+1\). Aquí\(\log\) significa logaritmo a la base 10. Así\({\mbox{\) (a)\(}}+1\) es una fórmula para el número de dígitos en\(a\).

(Pista: para probar la ecuación, mostrar que si la ecuación se\(\eqref{decimalrep}\) mantiene con\(a_{n-1}\neq 0\) entonces\(10^{n-1}\le a<10^n\). Entonces aplicar el\(\log\) a todos los términos de esta desigualdad. Esto está permitido ya que\(\log\) es una función creciente en el conjunto de números reales positivos.)

Ejercicio\(\PageIndex{10}\)

Utilice el ejercicio anterior para determinar el número de dígitos en la representación decimal del número\(2^{3321928}\).

(Pista: recuerda que\(\log(x^y)=y\log(x)\) cuando\(x\) y\(y\) son positivos.)

Ejercicio \(\PageIndex{11}\)

Recordemos que\(\log_b(a)\) significa el logaritmo de\(a\) con base\(b\). ¿Se pueden adaptar las ideas de Ejercicio\(\PageIndex{9}\) para encontrar una fórmula para el número de dígitos en la\(b\) representación base de\(a\)?