Zettelkasten

Común Divisor

Se lee en 10 min

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.

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.

Teorema.

Sean , o , y . Tenemos que

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,

Corolario.

Sean , o . Entonces,

Definición (Primos Relativos)

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

Teorema.

Sean con y , o bien . Si , entonces

Lema. (Lema de Euclides)

Sean . Si y , entonces

Vista Gráfica

Retroenlaces