<< DCM(A,B)=DCM(A-B,B)>>
|
<< 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
 OmaNet Curso CyM98 |
OmaNet - Educación Interactiva www.oma.org.ar/omanet | omanet@oma.org.ar |
| mensajes: webmaster@oma.org.ar |