Skip to content

Máximo común divisor y algoritmo de Euclides

January 26, 2012

Para un entero positivo k, llamamos Dk al conjunto de todos sus divisores positivos. De esta forma, para enteros positivos m, y n, el elemento máximo de Dm ∩ Dn, es el máximo común divisor de m y n, o mcd(m,n). Si mcd(m,n)=1, decimos que m y n son coprimos. Algunas propiedades básicas son:

  1. Si p es un primo, entonces mcd(p,m)=p o mcd(p,m)=1. En efecto, los divisores de p son p y uno, por lo que los divisores comunes de p, y m serán p o 1.
  2. Si d=mcd(m,n), m=dm’, n=dn’, entonces mcd(m’,n’)=1. En efecto, todos los divisores comunes de m, n, son d, luego la descomposición factorial de m’ no tiene divisores comunes de m, n, solo los de m y que no están en n. Por tanto, m es coprimo com n.
  3. Si d=mcd(m,n), m=d’m”, n=d’n”, mcd(m”,n”)=1, entonces d’=d. Si mcd(m”,n”)=1, significa que m”, y n” no tienen divisores comunes. Como n tiene entre sus divisores a d, n”d’=n implica que d’=d.
  4. Si d’ es un divisor común de m y n, entonces d’ divide a d=mcd(m,n). La factorización de d’ contiene solo a divisores comunes de m, n. Como d los contiene todos, d’|d
  5. Si m=nq+r, entonces, mcd(m,n)=mcd(n,r). Sea d=mcd(m,n), y d’=mcd(n,r). Como d|m y d|n, entonces d|r, luego d|d’. De la misma forma, d’|n y d’|r, luego d’|m, por lo que d’|d. Por tanto d=d’.

 

La propiedad (5), nos permite construir el algoritmo de Euclides, que es un método para obtener el mcd de dos números repitiendo varias divisiones:

m=nq1+r1

n=r1q2+r2

.

.

rk-2=rk-1qk+rk

rk-1=rkqk+1

Donde rk es el mcd(m,n), pues mcd(m,n)=mcd(n,r1)=mcd(r1,r2)=…=mcd(rk-1,rk)=rk.

Además, despejando rk en función de m y n, es decir rk=am+bn, podemos enunciar el siguiente teorema: Para dos enteros positivos m, n, existen enteros, a, b, tales que ma+nb=mcd(m,n). Teorema del cuál se sigue que si a|bc, y mcd(a,b)=1, entonces a|c, pues ax+by=1 para algunos x, e y, luego axc+byc=c, y como a|axc y a|aby, entonces a|c.

About these ads

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: