8 Divisibilidad en . Algoritmo de Euclides.
Definición 8.1.
Sea
Proposición 8.1.
-
1.
(desigualdad triangular) -
2.
Demostración.
Demostrar por nuestra cuenta (facil). ∎
Definición 8.2 (Cotas superiores e inferiores, maximos y minimos).
Sea
-
es cota superior de si . -
es cota inferior de si . -
Si
es una cota superior de y ademas , decimos que es el maximo de . -
Si
es una cota inferior de y ademas , decimos que es el minimo de .
Ejemplo.
Sea
-
.-
•
son ejemplos de cotas inferiores de . -
•
es el minimo de . -
•
son ejemplos de cotas superiores de . -
•
es el maximo de .
-
•
-
-
•
son ejemplos de cotas inferiores de . -
•
es el minimo de . -
•
no esta acotado superiormente. -
•
no tiene maximo.
-
•
Proposición 8.2.
En
-
Todo conjunto no vacio y acotado inferiormente tiene minimo.
-
Todo conjunto no vacio y acotado superiormente tiene maximo.
Demostración.
Obvio. ∎
Ejemplo.
Este resultado no es cierto en otros conjuntos ordenados. Por ejemplo
-
Sea
.≔ -
son ejemplos de cotas inferiores. -
no tiene minimo. 1 es el infimo de . -
son ejemplos de cotas superiores. -
no tiene maximo.
Teorema 8.1 (de la división entera).
Sean
-
1.
-
2.
Ademas
Demostración.
No demostrada en clase. ∎
Ejemplo.
-
1.
-
2.
X -
3.
-
4.
Definición 8.3 (Divisor, multiplo).
Sean
Proposición 8.3 (Propiedades de la relacion de divisibilidad).
-
1.
-
2.
-
3.
-
4.
-
5.
-
6.
-
7.
-
8.
-
9.
-
10.
Demostración.
-
1.
-
2.
Supongamos que
tal que , pero tenemos que . Hemos llegado a una contradiccion, luego (revisar) -
3.
tal que tal que . -
4.
-
5.
tal que tal que -
6.
Tomo en 5) y obtengo el resultado. -
7.
-
a)
-
b)
tal que .
-
a)
-
8.
tal que tal que -
9.
tal que Tomo valor absoluto: Como , y -
10.
Supongamos que
y .- Caso 1
-
Si
- Caso 2
-
Si
Por 4, , . Luego .
Obs: no puede pasar
o por (2).
∎
Corolario 8.1.
La relacion de divisibilidad es una relacion de orden parcial en
Definición 8.4 (Numero primo).
Sea
Teorema 8.2.
Sea
Demostración.
Esto es una contradiccion. Luego uno de los dos es menor o igual que
Teorema 8.3 (Teorema fundamental de la aritmetica).
Sea
-
Existencia:
primos tal que -
Unicidad: Si
y donde los y son primos, entonces:-
•
-
•
Se pueden reordenar los factores de manera que
-
•
Demostración.
La existencia se puede demostrar por induccion completa, como vimos en la demostración (Ejemplo). La unicidad se demuestra más adelante. ∎
Teorema 8.4.
Hay infinitos numeros primos.
Demostración.
Demostrado en (2.4). ∎
Definición 8.5 (Maximo comun divisor).
Sean
Proposición 8.4 (Existencia m.c.d).
Demostración.
Sea
Definición 8.6.
Sean
Proposición 8.5.
-
1.
-
2.
-
3.
Demostración.
-
1.
es el divisor mas grande de y ademas divide a 0 -
2.
Es porque los divisores positivos de
son los mismos que los divisores positivos de . -
3.
Se debe a que los divisores de un numero positivo son menores o iguales que ese numero.
∎
Proposición 8.6.
Sean
Demostración.
Ejemplo.
Calcular el m.c.d. de 250 y 32.
Teorema 8.5 (Algoritmo de Euclides).
Sean
-
≔ -
≔ -
Sea
. Supongamos que ya hemos construido todos los elementos de la sucesion hasta Si construimos como el resto de la division entera de entre (es decir, tal que para algun y )
Entonces se cumple:
-
-
Demostración.
Vamos a ver que
Si consideramos el conjunto
Teorema 8.6 (Existencia de identidad de Bezout).
Sean
Definicion: A cualquier igualdad de la forma anterior se le llama identidad de Bezout entre
Ejemplo.
Vamos a ver como calcular una identidad de Bezout entre 224 y 92 (anteriormente hemos calculado
Demostración.
Despues de construir la sucesion de restos
Observación.
Si queremos generalizar la existencia de identidades de Bezout para enteros
-
Si
basta con calcular una identidad de Bezout para y y luego “mover” los signos a los coefientes. -
Las identidades de Bezout si alguno o los dos enteros son 0 son triviales de obtener.
Ejemplo.
Supongamos que quiero una identidad de Bezout entre
Id. Bezout entre
Si quiero una identidad de Bezout entre
Sea
Teorema 8.7.
Sean
Demostración.
Tenemos que demostrar que
∎
Lema 8.8 (de Euclides).
Sean
Demostración.
Por la existencia de identidades de Bezout,
∎
Corolario 8.1.
Sean
Demostración.
Por induccion sobre el numero de factores.
Si
-
1.
. Ya esta. -
2.
. Voy a justificar que . Los unicos divisores posibles positivos de son y (porque es primo). Como la unica opcion para el . Aplico el lema de Euclides tal que .
∎
Demostración.
Unicidad del teorema fundamental de la aritmetica.
Supongamos
Definición 8.7.
Sean
Proposición 8.7.
Demostración.
Los multiplos comunes positivos de
Proposición 8.8.
Demostración.
Llamamos
Lema 8.9.
Sean
Demostración.
Queremos probar que