Maximo comun divisor
Hola! Necesito probar el siguiente teorema:
Sean a y b enteros, no simultáneamente iguales a cer, y sea
d=ax0+by0 el numero positivo menor de la forma: ax+by (x,y son enteros).
Demostrar que d=(a, b), de es el máximo común divisor.
Sean a y b enteros, no simultáneamente iguales a cer, y sea
d=ax0+by0 el numero positivo menor de la forma: ax+by (x,y son enteros).
Demostrar que d=(a, b), de es el máximo común divisor.
1 respuesta
Respuesta de Valero Angel Serrano Mercadal
1
Es cierto. Sean dos números naturales a, b y sea de su máximo común divisor que denotaremos así d=mcd(a, b).
Supongamos que uno de ellos es cero, sin perder generalidad el b
mcd(a,0)=a; d=1a+0 y es el número positivo más pequeño que puede obtenerse con la combinacion ax+by
Supongamos ahora que son distintos de cero.
El número a podrá expresarse como producto de d=mcd(a, b) por otro y b también.
a=de
b=df
Entonces las combinaciones dex+dfy serán d(ex+fy), es decir que siempre serán múltiplo de d y por lo tanto el valor positivo mínimo que pueden tener es d.
Quedaría solo por demostrar que en efecto existen valores x,y tales que ax+by=d. Pero eso ya está demostrado, es el Lema de Bezout, puedes verlo aquí:
http://es.wikipedia.org/wiki/Lema_de_Bezout
Si quieres profundizar pincha el enlace al algoritmo extendido de Euclides, aunque no es una demostración sencilla. Pero esta demostrado y lo que tu decías también queda demostrado.
Espero que te haya servido, no olvides puntuar o pedir alguna aclaración más.
Supongamos que uno de ellos es cero, sin perder generalidad el b
mcd(a,0)=a; d=1a+0 y es el número positivo más pequeño que puede obtenerse con la combinacion ax+by
Supongamos ahora que son distintos de cero.
El número a podrá expresarse como producto de d=mcd(a, b) por otro y b también.
a=de
b=df
Entonces las combinaciones dex+dfy serán d(ex+fy), es decir que siempre serán múltiplo de d y por lo tanto el valor positivo mínimo que pueden tener es d.
Quedaría solo por demostrar que en efecto existen valores x,y tales que ax+by=d. Pero eso ya está demostrado, es el Lema de Bezout, puedes verlo aquí:
http://es.wikipedia.org/wiki/Lema_de_Bezout
Si quieres profundizar pincha el enlace al algoritmo extendido de Euclides, aunque no es una demostración sencilla. Pero esta demostrado y lo que tu decías también queda demostrado.
Espero que te haya servido, no olvides puntuar o pedir alguna aclaración más.
