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

Demostrar por nuestra cuenta (facil).

Obvio.

No demostrada en clase.

1. 1.
   ​

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

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

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

3. 3.
   ​

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

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

   $c=b\cdot m=q\cdot n\cdot m\Rightarrow a\mid c$

4. 4.
   ​

   $a=1\cdot a\Rightarrow 1|a,a|a$

   $a=(-1)(-a)\Rightarrow-1\mid a,-a\mid a$

5. 5.
   ​

   $a|b\Rightarrow\exists n\in\mathbb{Z}$ tal que $b=a\cdot n$

   $c|d\Rightarrow\exists m\in\mathbb{Z}$ tal que $d=c\cdot m$

   $b\cdot d=a\cdot n\cdot c\cdot m\Rightarrow ac\mid bd$

6. 6.
   ​

   $a|b\Rightarrow a|bd$

   Tomo $c=1$ en 5) y obtengo el resultado.

7. 7.
   ​

   $c\neq 0$

   1. (a)
      ​

      $a|b\Rightarrow ac|bc$

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

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

8. 8.
   ​

   $a|b\Rightarrow\exists m\in\mathbb{Z}$ tal que $b=a\cdot m$

   $a|c\Rightarrow\exists n\in\mathbb{Z}$ tal que $c=a\cdot n$

   $bd+ce=a\cdot m\cdot d+a\cdot n\cdot e=a(md+ne)=a(md+ce)$

9. 9.
   ​

   $a|b\Rightarrow\exists m\in\mathbb{Z}$ tal que $b=a\cdot m$

   Tomo valor absoluto: $|b|=|a\cdot m|=|a|\cdot|m|\geq|a|$

   Como $b\neq 0$, $m\neq 0$ y $|m|\geq 1$

10. 10.
    ​

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

    Caso 1

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

    Caso 2

    Si $a\neq 0,b\neq 0$

    Por 4, $a|b\Rightarrow|a|\leq|b|$, $b|a\Rightarrow|b|\leq|a|$. Luego $|a|=|b|$.

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

$\Leftarrow)$ Obvio. Si hay algun divisor $2\leq d\leq\sqrt{n}\Rightarrow d\neq 1,d\neq n\Rightarrow n$ es compuesto.

$\Rightarrow)$ $n\text{ compuesto}\Rightarrow\exists d_{1}\text{ divisor positivo de }n\text{ tal que }d_{1}\neq 1,d_{1}\neq n$.

Como $d_{1}$ es divisor de $n\Rightarrow\exists d_{2}\in\mathbb{N}$ tal que $n=d_{1}\cdot d_{2}$.

Sabemos que $d_{1}\geq 2$. Tambien $d_{2}\geq 2$ (porque, si no, $d_{1}$ seria $n$).

Lo demostramos por reduccion al absurdo. Supongamos que ambos, tanto $d_{1}$ como $d_{2}$ son mayores que $\sqrt{n}$:

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

La existencia se puede demostrar por induccion completa, como vimos en la demostración (4.4).

La unicidad se demuestra más adelante.

Demostrado en (2.7).

Sea $D=\left\{n\in\mathbb{N}\mid n\text{ es divisor comun de }a\text{ y }b\right\}$.

Supongamos, sin perdida de generalidad, que $a\neq 0$. Todos los elementos de $D$ son $\leq|a|$.

Luego $|a|$ es una cota superior de $D$. Por tanto $D$ tiene maximo.

Ese numero es el maximo comun divisor de $a$ y $b$.

Observacion: Estamos usando que $D\neq 0$ porque $1\in D$.

1. 1.
   ​

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

2. 2.
   ​

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

3. 3.
   ​

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

$a,b\in\mathbb{N}$, r es el resto de la division $a=bq+r$ y $a<r<b$.

Vamos a considerar $D_{1}=\left\{d_{1}\in\mathbb{N}\mid d_{1}\text{ es divisor comun de a y b}\right\}$ y $D_{2}=\left\{d_{2}\in\mathbb{N}\mid d_{2}\text{ es divisor comun de b y r}\right\}$.

Vamos a ver que $D_{1}=D_{2}$.

$\subseteq)$ Sea $d\in D_{1}\Rightarrow d_{1}$ es divisor de $a$ y $b\Rightarrow\exists m,n\in\mathbb{N}$ tal que $a=m\cdot d$ y $b=n\cdot d$.

Entonces $r=a-bq=m\cdot d-n\cdot d\cdot q\Rightarrow d(m-nq)\Rightarrow d|r$

Como tambien $d|b$, $d\in D_{2}$.

$\supseteq)$ Sea $d\in D_{2}\Rightarrow d|b$ y $d|r\Rightarrow\exists m,n\in\mathbb{N}$ tal que $b=d\cdot m,\;r=d\cdot n$.

Luego $a=bq+r=d\cdot q+d\cdot r=d(mq+n)\Rightarrow d|a$. Como tambien $d|b$, $d\in D_{1}$.

Como $D_{1}=D_{2}\Rightarrow\mathrm{m.c.d.}(a,b)=\mathrm{m.c.d.}(b,r)$

Vamos a ver que $\exists n\in\mathbb{N}$ tal que $r_{n}=0$.

Por reduccion al absurdo, supongamos que no existe. Tenemos una sucesion infinita de restos decrecientes

Si consideramos el conjunto $R=\left\{r_{i}\mid i\in\mathbb{N}\cup\left\{0\right\}\right\}$

$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.29, tenemos que $\mathrm{m.c.d.}(a,b)=\mathrm{m.c.d.}(r_{0},r_{1})=\mathrm{m.c.d.}(r_{1},r_{2})=\mathrm{m.c.d.}(r_{n-1},r_{n})=\mathrm{m.c.d.}(r_{n-1},0)=r_{n-1}$.

Despues de construir la sucesion de restos $r_{0},r_{1},r_{2},\ldots,r_{n-1}$ del algoritmo de Euclides, sabemos que $\mathrm{m.c.d.}(a,b)=r_{n-1}$ que por el teorema de la division $r_{n-1}=r_{n-3}+q_{n-1}r_{n-2}$.

Se puede escribir como combinacion lineal de $r_{n-3}$ y $r_{n-2}$. A su vez, $r_{n-2}$ se puede poner como combinacion lineal de $r_{n-3}$ y $r_{n-4}$. Sustituyendo conseguimos $r_{n-1}$ como combinacion lineal de $r_{n-3}$ y $r_{n-4}$.

Y sucesivamente hasta obtener $r_{n-1}$ como combinacion lineal de $a$ y $b$.

Tenemos que demostrar que $d\mathbb{Z}\overset{?}{=}\left\{au+bv\mid u,v\in\mathbb{Z}\right\}=E$, siendo $d=\mathrm{m.c.d.}(a,b)$.

$\subseteq)$ Sea $x\in d\mathbb{Z}\Rightarrow\exists y\in\mathbb{Z}$ tal que $x=dy$.

Por el teorema de existencia de identidades de Bezout, sabemos que existen $u_{1},v_{1}\in\mathbb{Z}$ tales que $d=a\cdot u_{1}+b\cdot v_{1}$.

Entonces $x=(a\cdot u_{1}+b\cdot v_{1})\cdot y=a\cdot u_{1}\cdot y+b\cdot v_{1}\cdot y\Rightarrow x\in E$.

$\supseteq)$ Sea $x\in E\Rightarrow\exists u,v\in\mathbb{Z}$ tales que $x=a\cdot u+b\cdot v$. Como $d$ es divisor tanto de $a$ como de $b\Rightarrow\exists m,n\in\mathbb{Z}$ tales que $a=m\cdot d,b=n\cdot d$.

Por la existencia de identidades de Bezout, $\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 $n=1$, $p|a_{1}\Rightarrow p|{a_{1}}\ (\text{trivial}).$

H.I. Si $p|a_{1}\cdots a_{n}\Rightarrow\exists i\in\mathbb{N}\mid p|a_{i}$.

T.I. Supongamos que $p|a_{1}a_{2}\cdots a_{n}a_{n+1}$.

Dos casos:

1. 1.
   ​

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

2. 2.
   ​

   $p\nmid a_{n+1}$.

   Voy a justificar que $\mathrm{m.c.d.}(p,a_{n+1}=1)$.

   Los unicos divisores posibles positivos de $p$ son $1$ y $p$ (porque $p$ es primo).

   Como $p\nmid a_{n+1}$ la unica opcion para el $\mathrm{m.c.d.}(p,a_{n+1})=1$.

   Aplico el lema de Euclides $\Rightarrow p|a_{1}\cdots a_{n}\Rightarrow\exists i\in\mathbb{N}$ tal que $p|a_{i}$.

Unicidad del teorema fundamental de la aritmetica.

Supongamos $n=p_{1}\cdots p_{k}=q_{1}\cdots q_{m}$ con los $p_{i}$ y $q_{i}$ primos y supongamos que $m\geq k$.

Por el corolario 2 $\Rightarrow\exists i\in\mathbb{N}$ tal que $p_{i}\mid q_{i}$.

Sin perdida de generalidad, reordenando los factores voy a suponer que $p_{1}$ divide a $q_{1}$.

Como $q_{1}$ es primo, sus unicos divisores posibles son $1$ y $q_{1}$. Como $p_{1}>1$ por ser primo, la unica opcion es $p_{1}=q_{1}$.

Dividiendo la igualdad entre $p_{1}$, tenemos que $p_{2}\cdot p_{3}\cdots p_{k}=q_{2}\cdot q_{3}\cdots q_{m}$.

Repito el argumento con $p_{2}=q_{2}$. Simplificando $p_{3}\cdots p_{k}=q_{3}\cdots q_{m}$.

Repitiendo el argumento tenemos $p_{3}=q_{3},p_{4}=q_{4},\ldots,p_{k}=q_{k}$ y $1=q_{m+1}\cdot q_{m+2}\cdots q_{m}$.

Esto no puede pasar a menos que fuera $k=m$. Luego las dos factorizaciones tienen la misma cantidad de factores y las he podido reordenar para que $p_{i}=q_{i}$ para todo $i$.

Los multiplos comunes positivos de $a$ y $b$ estan acotados inferiormente por 0.

Ademas, es un conjunto no vacio ya que $ab$ es multiplo comun de ambos.

Por tanto, existe un minimo de los multiplos.

Llamamos $m=\mathrm{m.c.m.}(a,b)$, $d=\mathrm{m.c.d.}(a,b)$.

Quiero demostrar que $m=\frac{ab}{d}$.

Sea $x=\frac{a\cdot b}{d}$. Quiero probar que x es el $\mathrm{m.c.m.}(a,b)$.

$x=a\cdot\frac{b}{d}\Rightarrow a\mid x$

$x=\frac{a}{d}\cdot b\Rightarrow b\mid x$

Luego $x$ es un multiplo comun de $a$ y $b$.

Falta ver que es el minimo entre los multiplos comunes de $a$ y $b$. Sea $y$ un multiplo comun positivo de $a$ y $b\Rightarrow\exists u,v\in\mathbb{N}\mid y=a\cdot u,y=b\cdot v$.

$a\cdot u=b\cdot v$. Dividiendo entre $d$: $\frac{a}{d}\cdot u=\frac{b}{d}\cdot v$.

Por el lema 8.51, $\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$.

Como $\frac{a}{d}\mid\frac{b}{d}$ y $\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$ por el lema de Euclides $\frac{a}{d}\mid 1\Rightarrow\exists w\in\mathbb{N}$ tal que $v=w\cdot\frac{a}{d}$ .

Ademas, $y=b\cdot v=b\cdot w\cdot\frac{a}{d}=x\cdot w\geq x\Rightarrow y\geq x$

Por tanto, todos los multiplos comunes positivos de $a$ y $b$ son mayores o iguales que $x$, luego $x=\mathrm{m.c.d.}(a,b)$

Queremos probar que $\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$ donde $d=\mathrm{m.c.d.}(a,b)$.

Sea $x$ un divisor comun de $a$ y $b$ positivo.

$\exists u,v\in\mathbb{Z}$ tales que $\frac{a}{d}=x\cdot u$ y $\frac{b}{d}=x\cdot v$ $\Rightarrow a=x\cdot u\cdot d,b=x\cdot d\cdot v$

Como $xd$ es divisor comun de $a$ y $b$ tiene que ser menor o igual que su $\mathrm{m.c.d.}(a,b)=d\Rightarrow xd\leq d$.

La unica opcion es $x=1$. Luego $\mathrm{m.c.d.}(\frac{a}{d},\frac{b}{d})=1$