CyM98

<< DCM(A,B)=DCM(A-B,B)>>


Vamos a demostrar una igualdad que se necesita para el
algoritmo de Euclides que dice que:

si A y B son enteros entonces DCM(A,B) = DCM(A-B,B)

Vamos a dividir la demostración en dos pedazos,

Para facilitar la escritura vamos a llamar D al divisor común mayor entre A y B, o sea D=DCM(A,B). Entonces como D es divisor de A y de B se pueden escribir a estos números como A=D*a y B=D*b en donde a y b son dos números enteros.

De esta manera DCM(A-B,B) =DCM(D*a-D*b,D*b) =DCM(D*(a-b),D*b) = D*DCM(a-b,b) = DCM(A,B)*DCM(a-b,b) o sea que DCM(A-B,B) es un múltiplo de DCM(A,B)

Es casi igual que la anterior. Para simplificar un poco llamo C=A-B y entonces debería probar que DCM(C,B) es un divisor de DCM(C+B,B). El resto es igual que el caso anterior reemplazando el signo menos por un más.

 

Por lo tanto DCM(A,B) es un divisor de DCM(A-B,B) y DCM(A-B,B) es un divisor de DCM(A,B). Entonces puedo tomar K y J enteros de manera que DCM(A,B)*K=DCM(A-B,B) y DCM(A-B,B)*J=DCM(A,B), y entonces DCM(A,B)*K*J=DCM(A,B). Así que si DCM(A,B) no es cero entonces K*J=1 y entonces K y J valen 1 o -1, como el DCM no es negativo entonces K y J tienen que ser 1 y entonces los dos DCM son iguales.


Lecciones relacionadas:


Divisor Común Mayor Factorizando

Algoritmo de Euclides


Comentarios, preguntas, sugerencias:

Nombre y apellido (opcional):

E-mail (opcional):

    


OmaNet   Curso CyM98 OmaNet - Educación Interactiva
   
www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar
duty free alcohol duty free cigarette buy cigars online where to buy cosmetics wholesale buy duty free perfumes buy duty free tobacco