Aritmética Modular y Grupos Permutación

1 enero, 20179 marzo, 2017Oscar Rosas Deja un comentario

Congruencias

Clases Congruencia Módulo n

“ Las clases de congruencia modulo n son los conjuntos de enteros que tienen el mismo resto en la división entre n. ”

Los enteros se reparten entre pares e impares, pero también en vez de repartir los enteros según su residuo en la división entre 2, podemos repartirlos según su residuo en la división entre 3, entre 4 . . . entre cualquier entero n ≥ 2.

Por ejemplo, hay tres residuos posibles en la división entre 3, y los enteros se reparten según su residuo en los tres conjuntos siguientes:

Son los conjuntos de enteros que tienen el mismo resto en la división entre n. Si a es un entero, notamos su clase de congruencia módulo n.

Notación para el conjunto de las clases de congruencia modulo n

Sea n un entero. Notamos el conjunto de las clases de congruencia módulo n. Si n>0.

Congruencia Módulo n

De esta manera podemos definir la congruencia módulo n como:

a y b son congruentes módulo n si pertenecen a la misma clase de congruencia módulo n, es decir, si tienen el mismo resto en la división entre n.
Si n > 1. Dos enteros a y b son congruentes módulo n si y sólo si su diferencia es un múltiplo de n.

En regla general, si es un entero positivo, hay clases de congruencia módulo n, que son:

La clase es exactamente el conjunto de todos los enteros de la forma para .

Aritmética Modular

Sabemos que la suma de dos enteros pares siempre es par, la suma de dos enteros impares siempre es impar, y que la suma de un entero par y de un entero impar siempre es impar. Resumimos estas leyes de la manera siguiente:

El conjunto tiene tres elementos:

Si, por ejemplo, y entonces siempre se tiene y

Reglas Generales

Sea n en entero. Sean y dos clases módulo n.

Todas las sumas de un elemento de y de un elemento de están en una misma clase modulo n.

Todos los productos de un elemento de y de un elemento de están también en una misma clase modulo n.

Operaciones

Suma: A + B = (A+B) % n

Resta: A – B = (A-B) % n

Multiplicación: A * B = (A*B) % n

Función $\varphi$ de Euler

Teorema de Euler

Pequeño teorema de Fermat

Teorema Chino del residuo

Problemas diversos

Grupos Permutación

Estos grupos son algo muy importantes en Matemáticas:

Esta configuración inicial, la cual identificaremos como la permutación identidad I, usualmente se representa en los textos de matemáticas de la siguiente manera:

Relaciones y Funciones

1 enero, 201717 abril, 2017Oscar Rosas Deja un comentario

En álgebra y cálculo son importantes las relaciones entre variables; en geometría lo son las relaciones entre figuras.

Definición

Sean y conjuntos. Una relación de en es un subconjunto de , es decir:

Si , decimos simplemente que es una relación en .

Dominio y Contradominio

Dominio

Imagen – Contradominio

Relación Inversa

Reflexiva y Irreflexiva

Relación Reflexiva

» a tiene que estar relacionada con a, sin importar que a también está relaciona con otros elementos»

Relación Irreflexiva

Relación Identidad

Relación Cerradura Reflexiva

Es una relación que cumple con:

Simetría y Antisimetría

Simetría

Antisimetría

Relación Cerradura Simétrica

Es una relación que cumple con:

Transitividad

Si decimos que es transitiva entonces:

Relación Cerradura Transitiva

Es una relación que cumple con:

Funciones

Una función es una relación que cumple con las siguientes 2 condiciones:

“Todo los elementos del dominio tienen un valor asignado”

Para toda a que pertenece a A existe una b que pertenece a B es tal que:

“A cada valor del dominio solo le corresponde un único elemento del contradominio”

Si entonces

Gráficamente para que una relación sea función toda línea vertical debe tocar mínimo un punto de la gráfica y no más de un punto.

No son funciones

Es función

Tipos de Funciones

Funciones Continuas

Funciones incontables, y que pueden tomar cualquier valor como los Reales

Funciones Discretas Finitas

Funciones en las que solo pueden tomar valores selectos y son contables, como {1,34,1}

Funciones Discretas Infinitas

Funciones en las que solo pueden tomar valores selectos, pero son incontables, como los Naturales

Funciones Inyectivas

Funciones en las que solo le corresponde un elemento del conjunto A en el conjunto B. Una función es inyectiva si a cada valor del conjunto (dominio) le corresponde un valor distinto en el conjunto (imagen).

Es decir, a cada elemento del conjunto A le corresponde un solo valor tal que, en el conjunto A no puede haber dos o más elementos que tengan la misma imagen.

De forma gráfica: Si hay un punto en la función en el que pasa por dos puntos de una línea horizontal no es inyectiva.

Funciones Suprayectiva

Funciones en las que cada elemento del contradominio tiene un elemento en A. Una función es suprayectiva si está aplicada sobre todo el codominio, es decir, cuando la imagen , o en palabras más sencillas, cuando cada elemento de «Y» es la imagen de como mínimo un elemento de «X».

De forma gráfica: Si hay un punto en la función en el una línea horizontal no toque a la función no es suprayectiva.

Funciones Biyectiva

Funciones que son al mismo tiempo inyectivas y suprayectiva

…

* Tú, después de Relaciones y Funciones en Matemáticas Discretas*

Números Enteros

1 enero, 201712 febrero, 2017Oscar Rosas Deja un comentario

En esta lección me voy a centrar en los números enteros, pero antes de eso, creo apropiado hablarles de lo que hay más allá:

Naturales
Enteros
Racionales
Irracionales
Reales

Pero déjame los ordeno para ti, para que sea más fácil:

Reales: Conjunto que es la unión de los dos de abajo
- Racionales: Conjunto de números que se pueden expresar como una fracción
  - Enteros: Son un pequeño conjunto dentro de los racionales, que son lo que veremos
    - Naturales: Son los números enteros mayores a 0.
- Irracionales: Conjunto de números que NO se pueden expresar como una fracción.

Naturales

Los naturales son muy importantes para los matemáticos, si principal razón es que estos son la base de trabajo de la arma más poderosa de todos los matemáticos: La Inducción Matemática, da click y aprende de ella.

¿Los naturale incluyen el 0?

Eso siempre se me olvida, y después de preguntarles a varios matemáticos me dijeron que…NO.

Los Naturales Puros no incluyen el cero
Los Naturales Ampliados si que lo hacen

Esos tipos siempre tienen la respuesta a todo

Divisibilidad

Este concepto es algo difícil (al menos para mi) de comprender pero se puede sintetizar en que división de ambos pertenece a los números enteros, (ósea que es entero pues).

De manera formal, sean $a, b$ números enteros. Decimos que $a$ divide a $b$ si existe otro entero $q$ tal que $b=aq$ . La notación que usaremos para decir que $a$ divide a $b$ será $a \mid b$ . Algunas propiedades de la divisibilidad son:

Usualmente también decimos, para la notación $a \mid b$ , que $b$ es divisible entre $a$ , o que $b$ es múltiplo de $a$ .

Algoritmo de la división

Nosotros venimos dividiendo desde la primaria, en donde si queríamos dividir a $a$ entre $b$ , obteníamos un cociente (llamémosle $q$ ) y residuo (llamémosle $r$ ). Pues de manera algebráica, estos cuatro números cumplen con la relación $a=bq+r$ , donde $0 \leq r < \lvert b \rvert$ .

Vemos que la primera relación, básicamente nos dice cuántas veces cabe $b$ en $a$ sin pasarse y, para que se cumpla esto último, requerimos que el residuo $r$ sea un entero menor a $\lvert b \rvert$ pero mayor o igual a cero, de ahí la segunda relación.

Resulta evidente (pero esto no es obvio, se demuestra por inducción), que para cualesquiera $a,b \in \mathbb{Z}$ con $b \neq 0$ existen $q,r \in \mathbb{Z}$ únicos que cumplen con lo anterior.

Ejemplo. Efectúa la división de 47 entre 6. Vemos que el 6 cabe 7 veces en el 47 sin pasarse y sobran 5. Entonces, $47=6 \times 7+5$ , así $q=7$ y $r=5$ .

Cuando tenemos que efectuar la división con números negativos, tenemos que cuidar que ambas condiciones se sigan cumpliendo, en especial la de $0 \leq r < \lvert b \rvert$ .

Números primos

Decimos que un $p \in \mathbb{Z}$ es primo si:

$p > 1$ .
Sea $q \in \mathbb{N}$ . Si $q \mid p$ , entonces $q=1$ o $q=p$ .

Es decir, todos los números primos son mayores o iguales a 2 y solo los naturales $1$ y $p$ dividen a $p$ .

Sean $a,b \in \mathbb{Z}$ . Decimos que $a$ y $b$ son primos relativos si no existe un $p \in \mathbb{Z}$ primo tal que $p \mid a$ y $p \mid b$ .

Máximo Común Divisor

Este concepto es algo intuitivo, ya que se refiere al máximo numero natural que sea capaz de dividir a otros dos números enteros $a$ y $b$ . Pero ni modo, también tenemos que formalizar lo anterior y queda así:

Sean $a, b \in \mathbb{Z}$ . Decimos que $d \in \mathbb{Z}$ es el máximo común divisor de $a$ y $b$ si:

$d > 0$ .
$d \mid a$ y $d \mid b$ .
Sea $q \in \mathbb{Z}$ tal que $q \mid a$ y $q \mid b$ , entonces $q \mid d$ .

Usaremos la notación $d=(a,b)$ .

Ok, vayamos por partes entendiendo cada punto de la definición:

El primero es sencillo, quien quiera ser el máximo común divisor de $a$ y $b$ tiene que ser entero positivo, o natural simplemente. Digamos que nuestro candidato es $d$ .
Luego, obviamente, $d$ también tiene que dividir a $a$ y a $b$ , ¿si no por qué se llamaría común?
Finalmente, si llega algún otro entero $q$ que dice ser el máximo común divisor de $a$ y $b$ , tenemos que $q$ tiene que dividir a $d$ ; esto nos garantiza que $d$ sea en efecto el máximo común divisor.

Tenemos las siguientes propiedades, donde $a,b,c,p,q,r \in \mathbb{Z}$ y $p$ es primo:

Por convención, asumamos que $(0,0)$ es una indeterminación, para ahorrarnos problemas.
$(a,b)=(b,a)=(-a,b)$
Si $a \mid b$ , entonces $(a,b)=\lvert a \rvert$ .
Si $a \neq 0$ , entonces $(a,0)=|a|$ .
Si $a=bq+r$ , entonces $(a,b)=(b,r)$ .
$(ac,bc)=\lvert c \rvert (a,b)$
Si $a \mid bc$ y $(a,b)=1$ , entonces $a \mid c$
$(a, a+1)=1$
$p \mid a$ o $(a,p)=1$
Si $p \mid ab$ , entonces $p \mid a$ o $p \mid b$
$a$ y $b$ son primos relativos si y solo si $(a,b)=1$

Pero te preguntarás, ¿cómo puedo calcular $(a,b)$ de manera rápida, sin tener que recurrir al tanteo?

Algoritmo de Euclides

Sí, Euclides contribuyó también en teoría de números aparte de geometría. Sean $a,b \in \mathbb{Z}$ no ambos cero. Su algoritmo sirve para calcular $(a,b)$ con una repetida aplicación del algoritmo de la división.

Usaremos la quinta propiedad de la lista anterior, escogiendo $q$ y $r$ mediante el algoritmo de la división. Sin pérdida de generalidad asumamos que $a,b \geq 0$ y que $a \geq b$ . Debido a que $(a,b)=(b,r)$ y que $0 \leq r < b$ , usaremos recursividad para llegar a un punto en que tengamos que calcular algo como $(x,0)$ , y eso es igual a $x$ . Veamos cómo:

Comencemos asignando $r_0 \gets a$ , $r_1 \gets b$ y $i \gets 2$ .
Mientras :
- Sea esta la $i$ -ésima iteración.
- Efectuemos el algoritmo de la división para dividir $r_{i-2}$ entre $r_{i-1}$ , es decir, hallemos $q_i, r_i \in \mathbb{Z}$ tales que $r_{i-2}=r_{i-1}q_i+r_i$ con $0 \leq r_i < r_{i-1}$ .
- Aumentemos $i$ en $1$ (solo para llevar el orden del algoritmo).
Tenemos que $(a,b)=r_{i-2}$ .

Veamos un ejemplo:

Problema. Halla el máximo común divisor de $240$ y $46$ .

Solución. Comencemos asignando los residuos iniciales: $r_0=240$ y $r_1=46$ . Entonces:

$240=46 \times 5+10\\ 46=10 \times 4+6\\ 10=6 \times 1+4\\ 6=4 \times 1+2\\ 4=\boxed{2} \times 2+0$

Por lo tanto, $(240, 46)=2$ . Vemos que la secuencia de residuos que obtuvimos fue: $240, 46, 10, 6, 4, 2, 0$ ; y que el valor de $(240,46)$ es el último residuo distinto de cero.

Identidad de Bézout

Sean $a,b \in \mathbb{Z}$ no ambos cero, entonces existen $s,t \in \mathbb{Z}$ tales que $sa+tb=(a,b)$ . Es decir, existe una combinación lineal de $a$ y $b$ tal que es igual a su máximo común divisor.

Esta identidad es muy poderosa, ya que nos permite demostrar muchas proposiciones que involucran divisibilidad y máximo común divisor. Por ejemplo, tenemos el teorema que afirma que si existen $s, t \in \mathbb{Z}$ tales que $sa+tb=1$ , entonces $(a,b)=1$ .

Algoritmo extendido de Euclides

Este algoritmo nos sirve para hallar $s,t \in \mathbb{Z}$ que satisfagan la identidad de Bézout, además del mínimo común múltiplo de $a$ y $b$ . Vamos a proceder con base en el Algoritmo de Euclides, pero agregando unos pasos extra:

Comencemos asignando $r_0 \gets a$ , $r_1 \gets b$ , $s_0 \gets 1$ , $t_0 \gets 0$ , $s_1 \gets 0$ , $t_1 \gets 1$ y $i \gets 2$ .
Mientras :
- Sea esta la $i$ -ésima iteración.
- Efectuemos el algoritmo de la división para dividir $r_{i-2}$ entre $r_{i-1}$ , es decir, hallemos $q_i, r_i \in \mathbb{Z}$ tales que $r_{i-2}=r_{i-1}q_i+r_i$ con $0 \leq r_i < r_{i-1}$ .
- Asignemos $s_i \gets s_{i-2}-s_{i-1}q_i$ y $t_i \gets t_{i-2}-t_{i-1}q_i$
- Aumentemos $i$ en $1$ (solo para llevar el orden del algoritmo).
Tenemos que $s_{i-2}a+t_{i-2}b=r_{i-2}=(a,b)$ .

Tomemos de nuevo el ejemplo anterior, pero esta vez llevando los valores en una tabla:

$\begin{array}{|c|c|c|c|c|c|} \hline \text{Iteracion } (i) & \text{Algoritmo de la division} & q_i & r_i & s_i & t_i \\ \hline 0 & & & 240 & 1 & 0 \\ \hline 1 & & & 46 & 0 & 1 \\ \hline 2 & 240 = 46 \times 5 + 10 & 5 & 10 & 1 - 0 \times 5 = 1 & 0 - 1 \times 5 = -5 \\ \hline 3 & 46 = 10 \times 4 + 6 & 4 & 6 & 0 - 1 \times 4 = -4 & 1 - (-5) \times 4 = 21 \\ \hline 4 & 10 = 6 \times 1 + 4 & 1 & 4 & 1 - (-4) \times 1 = 5 & -5 - 21 \times 1 = -26 \\ \hline 5 & 6 = 4 \times 1 + 2 & 1 & 2 & -4 - 5 \times 1 = -9 & 21 - (-26) \times 1 = 47 \\ \hline 6 & 4 = 2 \times 2 + 0 & 2 & 0 & 5 - (-9) \times 2 = 23 & -26 - 47 \times 2 = -120 \\ \hline 7 & & & & & \\ \hline \end{array}$

Por lo tanto, $(-9)(240)+(47)(46)=2$ . De hecho nos pudimos haber ahorrado calcular $s_6$ y $t_6$ en la sexta iteración, ya que el residuo obtenido ahí ( $r_6$ ) es $0$ y con eso terminamos. Sin embargo, resulta que $\dfrac{a}{b}=-\dfrac{t_{i-1}}{s_{i-1}}$ , donde la fracción $\dfrac{t_{i-1}}{s_{i-1}}$ está en su mínima expresión. En este caso, $\dfrac{240}{46}=\dfrac{120}{23}$ . Otra utilidad más de este algoritmo, qué impresionante.

Ahora analicemos por qué funciona este poderoso algoritmo:

Básicamente primero aplicamos el algoritmo normal, y una vez que terminemos, vamos despejando los residuos de cada ecuación de tal forma que siempre queden como combinación lineal de $a$ y $b$ . Tomando el ejemplo de $a=240$ y $b=46$ tenemos que:

$240=46 \times 5+10 \Longrightarrow 10=(1)(240)+(-5)(46)$

$46=10 \times 4+6 \Longrightarrow 6=46-4(10)=46-4[(1)(240)+(-5)(46)]=(-4)(240)+(21)(46)$

$10=6 \times 1+4 \Longrightarrow 4=10-1(6)=[(1)(240)+(-5)(46)]-[(-4)(240)+(21)(46)]=(5)(240)+(-26)(46)$

$6=4 \times 1+2 \Longrightarrow 2=6-1(4)=[(-4)(240)+(21)(46)]-[(5)(240)+(-26)(46)]=(-9)(240)+(47)(46)$

De manera general, en cada iteración comenzando con $i=2$ queremos expresar $r_i$ como combinación lineal de $a$ y de $b$ , es decir, $r_i=s_i a+t_i b$ con $s_i, t_i \in \mathbb{Z}$ . Pero por definición de $r_i$ tenemos que $r_i=r_{i-2}-r_{i-1}q_i$ . Combinando ambas ecuaciones llegamos a:

$r_i=s_{i-2}a+t_{i-2}b-(s_{i-1}a+t_{i-1}b)q_i=(s_{i-2}-s_{i-1}q_i)a+(t_{i-2}-t_{i-1}q_i)b$

Por lo tanto, $s_i=s_{i-2}-s_{i-1}q_i$ y $t_i=t_{i-2}-t_{i-1}q_i$ . Ahora tenemos que hallar los valores iniciales de $s$ y $t$ , es decir, $s_0,t_0,s_1,t_1$ . Tenemos que:

$a=r_0=s_0 a+t_0 b \Longrightarrow s_0=1, t_0=0$

$b=r_1=s_1 a+t_1 b \Longrightarrow s_1=0, t_1=1$

Finalmente, supongamos que en la $i$ -ésima iteración tenemos $r_{i-1}=0$ . Como tenemos que dividir $r_{i-2}$ entre $r_{i-1}$ y no podemos dividir entre cero, nos detenemos ahí y vemos que:

$(a,b)=(r_0,r_1)=(r_1,r_2)=\cdots=(r_{i-2},r_{i-1})=(r_{i-2},0)=r_{i-2}=s_{i-2}a+t_{i-2}b$

Tenemos garantizado que este algoritmo siempre terminará, ya que la secuencia de los residuos es decreciente y en alguna iteración tendremos que $r_{i-1}=0$ , ya que por el algoritmo de la división, $0 \leq r_i < r_{i-1}$ para $i \geq 2$ , y generalizando a todos los residuos, $r_1 > r_2 > \cdots >r_{i-1}=0$ .

Ecuaciones diofánticas

Resulta que los enteros $s,t \in \mathbb{Z}$ que satisfacen la identidad de Bézout no son únicos, por ejemplo, tomando el caso de $240$ y $46$ también tenemos que $(14)(240)+(-73)(46)=2$ .

Supongamos que queremos hallar las soluciones enteras de la ecuación $ax+by=c$ , donde $a,b,c \in \mathbb{Z}$ . Esta ecuación tendrá soluciones enteras si y solo si $(a,b)|c$ .

Para ver que $(a,b)|c$ implica que la ecuación tenga soluciones enteras; vemos que existen $s,t \in \mathbb{Z}$ tales que $sa+tb=(a,b)$ , pero también $c=(a,b)k$ para alguna $k \in \mathbb{Z}$ , entonces $sak+tbk=(a,b)k=c$ , por lo que claramente una solución será $x=sk$ y $y=tk$ , donde $k=\dfrac{c}{(a,b)}$ .

Para ver que el hecho de que la ecuación tenga soluciones enteras implica que $(a,b)|c$ ; supongamos que la solución es $x=x_0$ y $y=y_0$ , así $ax_0+by_0=c$ . Pero $(a,b)|a$ y $(a,b)|b$ , entonces $(a,b)$ dividirá a cualquier combinación lineal de $a$ y $b$ , y qué mejor que divida justamente a $ax_0+by_0$ , así $(a,b)|ax_0+by_0$ , por lo tanto $(a,b)|c$ .

Veamos muchos ejemplos de lo anterior:

Problema. Determina si la ecuación $4x+10y=6$ tiene soluciones enteras, y en caso de tenerlas, halla una.

Solución. Al efectuar el algoritmo extendido de Euclides con $a=4$ y $b=10$ tenemos que $(4,10)=2=(-2)(4)+(1)(10)$ . En esta ecuación $c=6$ , y como $(4,10)|6$ , la ecuación sí tiene soluciones enteras. Tenemos que $s=-2$ , $t=1$ y $k=\dfrac{6}{(4,10)}=3$ , por lo que una solución será $x=(-2)(3)=-6$ y $y=(1)(3)=3$ .

Problema. Determina si la ecuación $6x+15y=7$ tiene soluciones enteras, y en caso de tenerlas, halla una.

Solución. Al efectuar el algoritmo extendido de Euclides con $a=6$ y $b=15$ tenemos que $(6,15)=3=(3)(6)+(-1)(15)$ . En esta ecuación $c=7$ , y como $(6,15) \nmid 7$ , la ecuación no tiene soluciones enteras.

Ahora, determinemos la estructura de las soluciones de este tipo de ecuaciones. Sea $x_0$ y $y_0$ una solución de la ecuación $ax+by=c$ , entonces $x=x_0+\dfrac{b}{(a,b)}k$ y $y=y_0-\dfrac{a}{(a,b)}k$ forman la familia de soluciones de la ecuación para toda $k \in \mathbb{Z}$ .

Para comprobar que esas son soluciones, basta con sustituirlas y ver que satistagan la ecuación:

$a\left(x_0+\dfrac{b}{(a,b)}k\right)+b\left(y_0-\dfrac{a}{(a,b)}k\right)=\\ax_0+\dfrac{ab}{(a,b)}k+by_0-\dfrac{ab}{(a,b)}k=ax_0+by_0=c$

(por la suposición de que $x_0$ y $y_0$ es una solución).

Por último, para demostrar que las soluciones anteriores en realidad nos dan todas las soluciones, supongamos que tenemos otra solución $(x,y)$ además de la inicial $(x_0,y_0)$ , entonces:

$ax+by=c \\ ax_0+by_0=c$

Restando obtenemos que:

$a(x-x_0)+b(y-y_0)=0 \Longrightarrow a(x-x_0)=b(y_0-y)$

Dividiendo entre $(a,b)$ obtenemos:

$\dfrac{a}{(a,b)}(x-x_0)=\dfrac{b}{(a,b)}(y_0-y)$

Vemos que $\dfrac{b}{(a,b)} \bigm| \dfrac{a}{(a,b)}(x-x_0)$ , pero como $\dfrac{b}{(a,b)}$ y $\dfrac{a}{(a,b)}$ son primos relativos, entonces $\dfrac{b}{(a,b)} \mid (x-x_0)$ , por lo que existe $k \in \mathbb{Z}$ tal que $x-x_0=\dfrac{b}{(a,b)}k$ , así $x=x_0+\dfrac{b}{(a,b)}k$ . Finalmente obtengamos $y$ al sustituir en la ecuación inicial:

$a(x-x_0)=b(y_0-y) \\ \dfrac{ab}{(a,b)}k=b(y_0-y) \\ \dfrac{a}{(a,b)}k=y_0-y \\ y=y_0-\dfrac{a}{(a,b)}k$

Ejemplo: retomando la ecuación $4x+10y=6$ , obtuvimos una solución inicial $(x_0,y_0)=(-6,3)$ , por lo tanto, la estructura de sus soluciones será:

$x=-6+\dfrac{10}{2}k=-6+5k$

$y=3-\dfrac{4}{2}k=3-2k$

$(x,y)=(-6+5k, 3-2k)$

Si tomamos $k \in \{0,1,2,3\}$ , obtendríamos las soluciones $(x,y)=(-6,3),(-1,1),(4,-1),(9,-3)$ .

Sistemas de numeración

Seguramente recordarás en cursos anteriores que descomponías un número en unidades, decenas, centenas, etc. Por ejemplo, en el número 468 tenemos 8 unidades, 6 decenas y 4 centenas. Igual recuerdas que el valor de un dígito depende de su posición, de hecho esta es la característica principal de los sistemas de numeración posicionales: el número 8 vale 8, el 6 vale 60 y el 4 vale 400; en efecto, 8+60+400=468.

De manera general, tomando un $x \in \mathbb{N}$ , podemos representarlo mediante sus $n+1$ dígitos en base 10 de la siguiente forma:

$\displaystyle x=\sum_{k=0}^{n} a_k {10}^k$

Donde todos los $a_k$ son dígitos, es decir, $0 \leq a_k < 10$ y $a_n \neq 0$ . Por ejemplo, $468=8 \cdot 10^0+6 \cdot 10^1+4 \cdot 10^2$ , por lo que $a_0=8$ , $a_1=6$ y $a_2=4$ .

Sin embargo, la definición anterior nos permite generalizar e introducir el concepto de un número $x$ de $n+1$ dígitos expresado en base $b$ , donde $b \geq 2$ y $0 \leq a_k < b$ :

$\displaystyle x=\sum_{k=0}^{n} a_k b^k$

Para identificar que $x$ está en base $b$ , escribiremos $x_b$ , excepto cuando $b=10$ , en donde simplemente escribiremos $x$ .

Ejemplo. Halla el valor de $13402_5$ en base 10.

Solución. Usando la definición tenemos que:

$\displaystyle 13402_5 = \sum_{k=0}^{4} a_k 5^k \\ =2 \cdot 5^0+0 \cdot 5^1+4 \cdot 5^2+3 \cdot 5^3+1 \cdot 5^4\\ =2+0+100+375+625=1102$

Al usar bases mayores a 10, usaremos las letras del abecedario. Por ejemplo, el conjunto de los dígitos en base 16 es $\{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\}$ , donde $A=10$ , $B=11$ y así sucesivamente.

Ahora, veamos cómo convertir un número $x \in \mathbb{N}$ en base 10 a cualquier base $b$ :

Asignamos $x_0 \gets x$ y $i \gets 0$ (solo para llevar el orden de las iteraciones).
Sea esta la $i$ -ésima iteración. Mediante el algoritmo de la división dividimos $x_i$ entre $b$ , es decir, obtenemos $x_{i+1},r_i$ tales que $x_i=bx_{i+1}+r_i$ con $0 \leq r_i < b$ .
Si $x_{i+1}=0$ vamos al paso 4, si no, asignamos $i \gets i+1$ y vamos al paso 2.
Tenemos que $\displaystyle x=\sum_{k=0}^{i} r_k b^k=\overline{r_i r_{i-1} \ldots r_1 r_0}_b$ . Es decir, concatenamos los residuos del último al primero para formar la representación en base $b$ de $x$ .