Común Divisor

Definción. (Común Divisor)

Sean , decimos que es un divisor común de y si

Observación.

• Siempre existen divisores comunes, por ejemplo el 1.
• Si o existe un divisor común que es mayor o igual que los demás.

Proof. , o . Consideramos Si y , ent. Si y , ent. En cualqueir caso, si y , se tiene que y así . Concluimos que y como , . Por el PBO, tiene un elemento mínimo, digamos con y . Si y tenemos que . Entonces

Recordamos que si y , ent. , ent. .
Así, a tiene sólo una cantidad finita de divisores.

Definición. (MCD)

Sean , con o , decimos que es el máximo común divisor de y si es el mayor de todos los divisores comunes de y , se denota o o , es decir,

Observaciones.

• Si o , existe . (la Obs. anterior)
• Si o , se tiene
• Sean o . Si son unidades, Ent.
• Si solo , tenemos

Ejemplo.

Sea y , y tenemos que .
Consideremos las combinaciones lineales enteras de y , es decir

Pero, ¿se puede construir todos los de esta combinación lineal?
NO, dando un contraejemplo:

Pero entonces, que números si podemos crear con esta comb. lineal?

En general, las combinaciones lineales enteras de y son los múltiplos de . Y la menor combinación lineal positiva de y es .

Algunas observaciones sencillas,

Lema.

Sea no vacío, cerrado bajo suma y bajo resta.

Proof.

Sea no vacío, cerrado bajo suma y bajo resta,

1. Como existe , y como es cerrado bajo resta, .
2. Sea , tenemos , pues y cerrado bajo resta.
3. Sea , sea , tenemos .
   Sea , tenemos .
   Sea , tenemos .

Lema.

Sea , cerrado bajo suma y resta. Entonces o bien existe un elemento positivo mínimo en , digamos , que divide a todo elemento de , ent

Proof.

Sea cerrado bajo suma y resta. Por Lema 1, . Así, si , se cumple.
Si , existe con . Por Lema 1, también . Alguno de o es positivo, ent. en hay elementos positivos.

Por el PBO tiene un elemento mínimo, digamos .
Sea . PD.
Por el algoritmo de la divición,

Tenemos que, dado y Lema 1.

Tenemos con . Como es el positivo mínimo de y , entonces no puede ser positivo y así .

En consecuencia, . También pues y por Lema 1, .

Teorema. (Identidad de Bézout)

Sean no nulos. El máximo común divisor de y es la comb. lineal positiva mínima de y , es decir

En particular existen tales que

Proof.

Sean no ambos nulos. Considero .
Notamos que pues .
Además es cerrado bajo suma y bajo resta, ya que si .

Ent.

También y y o , entonces .
Por el Lema 2, tiene un elemento positivo mínimo, digamos , que devide a todo elemento en .
PD.
Como divide a todo elemento en y , ent y , ent. .
Por otro lado, sabemos que ,

Corolario.

Sean no ambos nulos. Las siguientes condiciones son equvialentes:

2. es la comb. lineal positiva mínima de y .
3. , y , es comb. lineal de y .
4. , y , si y , ent. .

es, los demás divisores dividen al MCD.

Proof.

Sean , y no ambos nulos. (Teo. anterior).

Sea la comb. lineal positiva mínima de y , por el resultado previo divide a toda comb. lineal de y , en particular y .

Sea , y , es comb. lineal de y .
Sea tal que y .
PD. .
Como es comb. lineal de y

y como y , ent.

Nota!

Se puede generalizar y definir el máximo común divisor de más de dos números con al menos uno distinto de cero.

Teorema.

Sean , o , y . Tenemos que

Proof.

Sean , o , y

• Caso 1:

• Caso 2:

Definición. (Cociente)

Sean , . Si , sabemos que existe tal que . A se le llama el cociente de entre y se denota por .

Observación.

• Dicha es única

Teorema.

Sean , o , y . Si y entonces,

Proof.

Sean , o , .
Supongamos que y . Por propiedades del máximo común divisor tenemos que y entonces también .
Ahora, por Obs. 2 y teorema anterior,

Y por def.

Corolario.

Sean , o . Entonces,

Proof.

Usando el teorema anterior con

Definición (Primos Relativos)

Sean , o . Decimos que y son primos relativos o coprimos si .

Ejemplo.

28 y 55 son primos relativos ya que .

Teorema.

Sean con y , o bien . Si , entonces

Proof.

Sean , y , o bien .
Supongamos que . Sabemos que existen tales que

Lo que implica, que es una combinación lineal entera de y .
Dado que es la comb lineal entera positiva mínma de y , concluimos que

Lema. (Lema de Euclides)

Sean . Si y , entonces

Proof.

Sean , y no ambos nulos. Supongamos y . Como existen tales

Mult. por

Como ent. . Además, , ent.