Demostración máximo común divisor
Hola! Tengo que demostrar el siguiente Teorema:
Si d=(a, b) entonces de es la mínima combinación lineal de a y b.
Nota: d=(a, b) .. Quiere decir que de es el máximo común divisor de a y b.
Necesito una demostración sencilla pero convincente.
Si d=(a, b) entonces de es la mínima combinación lineal de a y b.
Nota: d=(a, b) .. Quiere decir que de es el máximo común divisor de a y b.
Necesito una demostración sencilla pero convincente.
Respuesta de jajo0494
1
Se puede demostrar por una contradicción:
suponga que p es la minima combinacion lineal de ax+by... entonces es posible escribir a a=pq+r con o<=r
<p entonces r=a(q-qx)+b(-yq) (despejando para r y sustituyendo p con ax+by), entonces r es combinacion lineal de a, b pero como r<p y p es la menor combinacion lineal entonces r=0 lo que quiere decir que p divide a.
de manera analoga se llega a que p divide b, entoces p divide a a,b.
entonces p divide a ax+by pero d divide a ax+by por lo que p>d contradiciendo la minimalidad entonces p=d.
suponga que p es la minima combinacion lineal de ax+by... entonces es posible escribir a a=pq+r con o<=r
<p entonces r=a(q-qx)+b(-yq) (despejando para r y sustituyendo p con ax+by), entonces r es combinacion lineal de a, b pero como r<p y p es la menor combinacion lineal entonces r=0 lo que quiere decir que p divide a.
de manera analoga se llega a que p divide b, entoces p divide a a,b.
entonces p divide a ax+by pero d divide a ax+by por lo que p>d contradiciendo la minimalidad entonces p=d.
