Números Enteros

fuentes2

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:

n1

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=1q=p.

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

Sean a,b \in \mathbb{Z}. Decimos que ab son primos relativos si no existe un p \in \mathbb{Z} primo tal que p \mid ap \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 aq \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 ab 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 ab, 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(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
  • ab 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 qr 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:

  1. Comencemos asignando r_0 \gets a, r_1 \gets b y i \gets 2.
  2. Mientras r_{i-1} \neq 0:
    • 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).
  3. 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:

  1. 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.
  2. Mientras r_{i-1} \neq 0:
    • 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).
  3. 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:

  1. Asignamos x_0 \gets x y i \gets 0 (solo para llevar el orden de las iteraciones).
  2. 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.
  3. Si x_{i+1}=0 vamos al paso 4, si no, asignamos i \gets i+1 y vamos al paso 2.
  4. 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.

Ejemplo. Convierte el número 16539 a base 7.

Solución. Tenemos que:

  • 16539 = 7 \times 2362 + 5
  • 2362 = 7 \times 337 + 3
  • 337 = 7 \times 48 + 1
  • 48 = 7 \times 6 + 6
  • 6 = 7 \times 0 + 6

Por lo tanto, 16539 = 66135_7.

Para convertir un número x de base b a base c, primero convertimos x_b a base 10 y luego a base c. Veamos cómo:

Ejemplo. Convierte el número 34215_6 a base 13.

Solución. Primero convirtamos 34215_6 a base 10. Tenemos que:

\displaystyle 34215_6 = \sum_{k=0}^{4}a_k 6^k \\ =5 \cdot 6^0+1 \cdot 6^1+2 \cdot 6^2+4 \cdot 6^3+3 \cdot 6^4\\ =5+6+72+864+3888=4835

Luego, convirtamos 4835 a base 13, tenemos que:

  • 4835 = 13 \times 371 + 12
  • 371 = 13 \times 28 + 7
  • 28 = 13 \times 2 + 2
  • 2 = 13 \times 0 + 2

Por lo tanto, 34215_6=227C_{13}.

btn1 btn
btn

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s