Números Enteros

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$ .