Lema de Euclides

Demostración

• Supongamos, sin pérdida de generalidad, que p es coprimo con a y veamos que p divide a b. Por definición, p y a

son coprimos si y sólo si mcd(a, p) = 1; y la identidad de Bézout nos asegura que existen números enteros x e y tales que:

${\displaystyle ax+py=1\,\!}$

• Que p divida a ab significa que existe un número entero r tal que pr = ab. Volviendo a la primera ecuación y multiplicando en ambos miembros por b, se obtiene:

${\displaystyle b(ax+py)=b\,\!}$

• y, en consecuencia

${\displaystyle bax+bpy=b\,\!}$

• Sabiendo que pr = ab, se obtiene

${\displaystyle prx+bpy=b\,\!}$

• sacando p como factor común, queda:

${\displaystyle p(rx+by)=b\,\!}$

• como rx+by es un número entero, se concluye que p divide a b. Q.E.D.