8 Divisibilidad en $\displaystyle\mathbb{Z}$. Algoritmo de Euclides.

Demostrar por nuestra cuenta (facil). ∎

Obvio. ∎

No demostrada en clase. ∎

1. 1.
   ​

   $\displaystyle\forall a\in\mathbb{Z}$ $\displaystyle\;a\mid 0?$

   $$\displaystyle 0=0\cdot a\Rightarrow a\mid 0$$
2. 2.
   ​

   Supongamos que $\displaystyle 0\mid a\Rightarrow\exists n\in\mathbb{Z}$ tal que $\displaystyle a=0\cdot n=0$, pero tenemos que $\displaystyle a=0$. Hemos llegado a una contradiccion, luego $\displaystyle 0\nmid a$ (revisar)

3. 3.
   ​

   $\displaystyle a\mid b\Rightarrow\exists n\in\mathbb{Z}$ tal que $\displaystyle b=q\cdot n$ $\displaystyle b\mid c\Rightarrow\exists m\in\mathbb{Z}$ tal que $\displaystyle c=b\cdot m$. $\displaystyle c=b\cdot m=q\cdot n\cdot m\Rightarrow a\mid c$

4. 4.
   ​

   $\displaystyle a=1\cdot a\Rightarrow 1|a,a|a$ $\displaystyle a=(-1)(-a)\Rightarrow-1\mid a,-a\mid a$

5. 5.
   ​

   $\displaystyle a|b\Rightarrow\exists n\in\mathbb{Z}$ tal que $\displaystyle b=a\cdot n$ $\displaystyle c|d\Rightarrow\exists m\in\mathbb{Z}$ tal que $\displaystyle d=c\cdot m$ $\displaystyle b\cdot d=a\cdot n\cdot c\cdot m\Rightarrow ac\mid bd$

6. 6.
   ​

   $\displaystyle a|b\Rightarrow a|bd$ Tomo $\displaystyle c=1$ en 5) y obtengo el resultado.

7. 7.
   ​

   $\displaystyle c\neq 0$

   1. a)
      ​

      $\displaystyle a|b\Rightarrow ac|bc$

      $$\displaystyle\begin{dcases}a|b\\c|c\end{dcases}\overset{5)}{\Rightarrow}ac|bc$$
   2. b)
      ​

      $\displaystyle ac|bc\Rightarrow\exists m\in\mathbb{Z}$ tal que $\displaystyle bc=acm\Rightarrow b=a\cdot m\Rightarrow a|b$.

8. 8.
   ​

   $\displaystyle a|b\Rightarrow\exists m\in\mathbb{Z}$ tal que $\displaystyle b=a\cdot m$ $\displaystyle a|c\Rightarrow\exists n\in\mathbb{Z}$ tal que $\displaystyle c=a\cdot n$ $\displaystyle bd+ce=a\cdot m\cdot d+a\cdot n\cdot e=a(md+ne)=a(md+ce)$

9. 9.
   ​

   $\displaystyle a|b\Rightarrow\exists m\in\mathbb{Z}$ tal que $\displaystyle b=a\cdot m$ Tomo valor absoluto: $\displaystyle|b|=|a\cdot m|=|a|\cdot|m|\geq|a|$ Como $\displaystyle b\neq 0$, $\displaystyle m\neq 0$ y $\displaystyle|m|\geq 1$

10. 10.
    ​

    Supongamos que $\displaystyle a|b$ y $\displaystyle b|a$.

    Caso 1

    Si $\displaystyle a=b=0\Rightarrow|a|=|b|$

    Caso 2

    Si $\displaystyle a\neq 0,b\neq 0$ Por 4, $\displaystyle a|b\Rightarrow|a|\leq|b|$, $\displaystyle b|a\Rightarrow|b|\leq|a|$. Luego $\displaystyle|a|=|b|$.

    Obs: no puede pasar $\displaystyle a=0,b\neq 0$ o $\displaystyle a\neq 0,b=0$ por (2).

∎

$\displaystyle\Leftarrow)$ Obvio. Si hay algun divisor $\displaystyle 2\leq d\leq\sqrt{n}\Rightarrow d\neq 1,d\neq n\Rightarrow n$ es compuesto. $\displaystyle\Rightarrow)$ $\displaystyle n\text{ compuesto}\Rightarrow\exists d_{1}\text{ divisor$. Como $\displaystyle d_{1}$ es divisor de $\displaystyle n\Rightarrow\exists d_{2}\in\mathbb{N}$ tal que $\displaystyle n=d_{1}\cdot d_{2}$. Sabemos que $\displaystyle d_{1}\geq 2$. Tambien $\displaystyle d_{2}\geq 2$ (porque, si no, $\displaystyle d_{1}$ seria $\displaystyle n$). Lo demostramos por reduccion al absurdo. Supongamos que ambos, tanto $\displaystyle d_{1}$ como $\displaystyle d_{2}$ son mayores que $\displaystyle\sqrt{n}$:

Esto es una contradiccion. Luego uno de los dos es menor o igual que $\displaystyle\sqrt{n}$. ∎

La existencia se puede demostrar por induccion completa, como vimos en la demostración (Ejemplo). La unicidad se demuestra más adelante. ∎

Demostrado en (2.4). ∎

Sea $\displaystyle D=\{n\in\mathbb{N}\mid n\text{ es divisor comun de }a\text{ y }b\}$. Supongamos, sin perdida de generalidad, que $\displaystyle a\neq 0$. Todos los elementos de $\displaystyle D$ son $\displaystyle\leq|a|$. Luego $\displaystyle|a|$ es una cota superior de $\displaystyle D$. Por tanto $\displaystyle D$ tiene maximo. Ese numero es el maximo comun divisor de $\displaystyle a$ y $\displaystyle b$. Observacion: Estamos usando que $\displaystyle D\neq 0$ porque $\displaystyle 1\in D$. ∎

1. 1.
   ​

   $\displaystyle|a|$ es el divisor mas grande de $\displaystyle a$ y ademas $\displaystyle|a|$ divide a 0 $\displaystyle\Rightarrow\mathrm{m.c.d.}(a,0)=|a|$

2. 2.
   ​

   Es porque los divisores positivos de $\displaystyle a$ son los mismos que los divisores positivos de $\displaystyle b$.

3. 3.
   ​

   Se debe a que los divisores de un numero positivo son menores o iguales que ese numero.

∎

$\displaystyle a,b\in\mathbb{N}$, r es el resto de la division $\displaystyle a=bq+r$ y $\displaystyle a<r<b$. Vamos a considerar $\displaystyle D_{1}=\{d_{1}\in\mathbb{N}\mid d_{1}\text{ es divisor comun de a$ y $\displaystyle D_{2}=\{d_{2}\in\mathbb{N}\mid d_{2}\text{ es divisor comun de b$. Vamos a ver que $\displaystyle D_{1}=D_{2}$. $\displaystyle\subseteq)$ Sea $\displaystyle d\in D_{1}\Rightarrow d_{1}$ es divisor de $\displaystyle a$ y $\displaystyle b\Rightarrow\exists m,n\in\mathbb{N}$ tal que $\displaystyle a=m\cdot d$ y $\displaystyle b=n\cdot d$. Entonces $\displaystyle r=a-bq=m\cdot d-n\cdot d\cdot q\Rightarrow d(m-nq)\Rightarrow d|r$ Como tambien $\displaystyle d|b$, $\displaystyle d\in D_{2}$. $\displaystyle\supseteq)$ Sea $\displaystyle d\in D_{2}\Rightarrow d|b$ y $\displaystyle d|r\Rightarrow\exists m,n\in\mathbb{N}$ tal que $\displaystyle b=d\cdot m,\;r=d\cdot n$. Luego $\displaystyle a=bq+r=d\cdot q+d\cdot r=d(mq+n)\Rightarrow d|a$. Como tambien $\displaystyle d|b$, $\displaystyle d\in D_{1}$. Como $\displaystyle D_{1}=D_{2}\Rightarrow\mathrm{m.c.d.}(a,b)=\mathrm{m.c.d.}(b,r)$ ∎

Vamos a ver que $\displaystyle\exists n\in\mathbb{N}$ tal que $\displaystyle r_{n}=0$. Por reduccion al absurdo, supongamos que no existe. Tenemos una sucesion infinita de restos decrecientes

Si consideramos el conjunto $\displaystyle R=\{r_{i}\mid i\in\mathbb{N}\cup\{0\}\}$ $\displaystyle R$ es un conjunto de enteros acotado inferiormente (por 0) pero que no tiene minimo. Esto es imposible. En cada paso de construccion de la sucesion, por la proposicion 8.6, tenemos que $\displaystyle\mathrm{m.c.d.}(a,b)=\mathrm{m.c.d.}(r_{0},r_{1})=\mathrm{m.c.d.}$. ∎

Despues de construir la sucesion de restos $\displaystyle r_{0},r_{1},r_{2},\ldots,r_{n-1}$ del algoritmo de Euclides, sabemos que $\displaystyle\mathrm{m.c.d.}(a,b)=r_{n-1}$ que por el teorema de la division $\displaystyle r_{n-1}=r_{n-3}+q_{n-1}r_{n-2}$. Se puede escribir como combinacion lineal de $\displaystyle r_{n-3}$ y $\displaystyle r_{n-2}$. A su vez, $\displaystyle r_{n-2}$ se puede poner como combinacion lineal de $\displaystyle r_{n-3}$ y $\displaystyle r_{n-4}$. Sustituyendo conseguimos $\displaystyle r_{n-1}$ como combinacion lineal de $\displaystyle r_{n-3}$ y $\displaystyle r_{n-4}$. Y sucesivamente hasta obtener $\displaystyle r_{n-1}$ como combinacion lineal de $\displaystyle a$ y $\displaystyle b$. ∎

Tenemos que demostrar que $\displaystyle d\mathbb{Z}\overset{?}{=}\{au+bv\mid u,v\in\mathbb{Z}\}=E$, siendo $\displaystyle d=\mathrm{m.c.d.}(a,b)$. $\displaystyle\subseteq)$ Sea $\displaystyle x\in d\mathbb{Z}\Rightarrow\exists y\in\mathbb{Z}$ tal que $\displaystyle x=dy$. Por el teorema de existencia de identidades de Bezout, sabemos que existen $\displaystyle u_{1},v_{1}\in\mathbb{Z}$ tales que $\displaystyle d=a\cdot u_{1}+b\cdot v_{1}$. Entonces $\displaystyle x=(a\cdot u_{1}+b\cdot v_{1})\cdot y=a\cdot u_{1}\cdot y+b\cdot v$. $\displaystyle\supseteq)$ Sea $\displaystyle x\in E\Rightarrow\exists u,v\in\mathbb{Z}$ tales que $\displaystyle x=a\cdot u+b\cdot v$. Como $\displaystyle d$ es divisor tanto de $\displaystyle a$ como de $\displaystyle b\Rightarrow\exists m,n\in\mathbb{Z}$ tales que $\displaystyle a=m\cdot d,b=n\cdot d$.

∎

Por la existencia de identidades de Bezout, $\displaystyle\exists u,v\in\mathbb{Z}\mid 1=a\cdot u+b\cdot v$. Multiplico por c:

∎

Por induccion sobre el numero de factores. Si $\displaystyle n=1$, $\displaystyle p|a_{1}\Rightarrow p|{a_{1}}\ (\text{trivial}).$ H.I. Si $\displaystyle p|a_{1}\cdots a_{n}\Rightarrow\exists i\in\mathbb{N}\mid p|a_{i}$. T.I. Supongamos que $\displaystyle p|a_{1}a_{2}\cdots a_{n}a_{n+1}$. Dos casos:

1. 1.
   ​

   $\displaystyle p|a_{n+1}$. Ya esta.

2. 2.
   ​

   $\displaystyle p\nmid a_{n+1}$. Voy a justificar que $\displaystyle\mathrm{m.c.d.}(p,a_{n+1}=1)$. Los unicos divisores posibles positivos de $\displaystyle p$ son $\displaystyle 1$ y $\displaystyle p$ (porque $\displaystyle p$ es primo). Como $\displaystyle p\nmid a_{n+1}$ la unica opcion para el $\displaystyle\mathrm{m.c.d.}(p,a_{n+1})=1$. Aplico el lema de Euclides $\displaystyle\Rightarrow p|a_{1}\cdots a_{n}\Rightarrow\exists i\in\mathbb{N}$ tal que $\displaystyle p|a_{i}$.

∎

Unicidad del teorema fundamental de la aritmetica. Supongamos $\displaystyle n=p_{1}\cdots p_{k}=q_{1}\cdots q_{m}$ con los $\displaystyle p_{i}$ y $\displaystyle q_{i}$ primos y supongamos que $\displaystyle m\geq k$. Por el corolario 2 $\displaystyle\Rightarrow\exists i\in\mathbb{N}$ tal que $\displaystyle p_{i}\mid q_{i}$. Sin perdida de generalidad, reordenando los factores voy a suponer que $\displaystyle p_{1}$ divide a $\displaystyle q_{1}$. Como $\displaystyle q_{1}$ es primo, sus unicos divisores posibles son $\displaystyle 1$ y $\displaystyle q_{1}$. Como $\displaystyle p_{1}>1$ por ser primo, la unica opcion es $\displaystyle p_{1}=q_{1}$. Dividiendo la igualdad entre $\displaystyle p_{1}$, tenemos que $\displaystyle p_{2}\cdot p_{3}\cdots p_{k}=q_{2}\cdot q_{3}\cdots q_{m}$. Repito el argumento con $\displaystyle p_{2}=q_{2}$. Simplificando $\displaystyle p_{3}\cdots p_{k}=q_{3}\cdots q_{m}$. Repitiendo el argumento tenemos $\displaystyle p_{3}=q_{3},p_{4}=q_{4},\ldots,p_{k}=q_{k}$ y $\displaystyle 1=q_{m+1}\cdot q_{m+2}\cdots q_{m}$. Esto no puede pasar a menos que fuera $\displaystyle k=m$. Luego las dos factorizaciones tienen la misma cantidad de factores y las he podido reordenar para que $\displaystyle p_{i}=q_{i}$ para todo $\displaystyle i$. ∎

Los multiplos comunes positivos de $\displaystyle a$ y $\displaystyle b$ estan acotados inferiormente por 0. Ademas, es un conjunto no vacio ya que $\displaystyle ab$ es multiplo comun de ambos. Por tanto, existe un minimo de los multiplos. ∎

Llamamos $\displaystyle m=\mathrm{m.c.m.}(a,b)$, $\displaystyle d=\mathrm{m.c.d.}(a,b)$. Quiero demostrar que $\displaystyle m=\frac{ab}{d}$. Sea $\displaystyle x=\frac{a\cdot b}{d}$. Quiero probar que x es el $\displaystyle\mathrm{m.c.m.}(a,b)$. $\displaystyle x=a\cdot\frac{b}{d}\Rightarrow a\mid x$ $\displaystyle x=\frac{a}{d}\cdot b\Rightarrow b\mid x$ Luego $\displaystyle x$ es un multiplo comun de $\displaystyle a$ y $\displaystyle b$. Falta ver que es el minimo entre los multiplos comunes de $\displaystyle a$ y $\displaystyle b$. Sea $\displaystyle y$ un multiplo comun positivo de $\displaystyle a$ y $\displaystyle b\Rightarrow\exists u,v\in\mathbb{N}\mid y=a\cdot u,y=b\cdot v$. $\displaystyle a\cdot u=b\cdot v$. Dividiendo entre $\displaystyle d$: $\displaystyle\frac{a}{d}\cdot u=\frac{b}{d}\cdot v$. Por el lema 8.9, $\displaystyle\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$. Como $\displaystyle\frac{a}{d}\mid\frac{b}{d}$ y $\displaystyle\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$ por el lema de Euclides $\displaystyle\frac{a}{d}\mid 1\Rightarrow\exists w\in\mathbb{N}$ tal que $\displaystyle v=w\cdot\frac{a}{d}$ . Ademas, $\displaystyle y=b\cdot v=b\cdot w\cdot\frac{a}{d}=x\cdot w\geq x\Rightarrow y\geqx$ Por tanto, todos los multiplos comunes positivos de $\displaystyle a$ y $\displaystyle b$ son mayores o iguales que $\displaystyle x$, luego $\displaystyle x=\mathrm{m.c.d.}(a,b)$ ∎

Queremos probar que $\displaystyle\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$ donde $\displaystyle d=\mathrm{m.c.d.}(a,b)$. Sea $\displaystyle x$ un divisor comun de $\displaystyle a$ y $\displaystyle b$ positivo. $\displaystyle\exists u,v\in\mathbb{Z}$ tales que $\displaystyle\frac{a}{d}=x\cdot u$ y $\displaystyle\frac{b}{d}=x\cdot v$ $\displaystyle\Rightarrow a=x\cdot u\cdot d,b=x\cdot d\cdot v$ Como $\displaystyle xd$ es divisor comun de $\displaystyle a$ y $\displaystyle b$ tiene que ser menor o igual que su $\displaystyle\mathrm{m.c.d.}(a,b)=d\Rightarrow xd\leq d$. La unica opcion es $\displaystyle x=1$. Luego $\displaystyle\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$ ∎