Lema d'Euclides
En matemàtiques, el lema d'Euclides és un lema que enuncia una propietat fonamental dels nombres primers. Concretament diu que si un nombre primer p divideix el producte ab i no divideix a llavors divideix b. Per exemple, la multiplicació 133⋅143 = 19019. Com que 19019 és divisible per 19, un dels dos factors, o bé 133 o bé 143 ho ha de ser també. De fet, 133 és divisible per 19 perquè 133/19 = 7.
Per als nombres compostos no es compleix aquesta propietat. Per exemple, 4 no divideix 6 i tampoc no divideix 10, però sí que divideix el seu producte 60 perquè 60/4 = 15.
Aquesta propietat és clau per demostrar el teorema fonamental de l'aritmètica. En teoria d'anells aquesta propietat s'utilitza per a generalitzar el concepte de nombre primer en els elements primers i ideals primers d'un anell commutatiu qualsevol.
El lema duu el nom del matemàtic grec Euclides perquè el primer lloc on apareix és a la proposició 30 del llibre vii dels Elements.
Demostració modifica
Si p divideix ab vol dir que existeix un nombre enter n > 1 tal que ab = np. La demostració del lema d'Euclides es fa trobant un nombre enter m tal que b = mp.
El primer pas serà trobar dos nombres enters x, y tals que 1 = xa + yp que és el que s'anomena la identitat de Bézout.
Un cop s'hagin trobat aquests dos nombres multiplicant per b els dos termes de la igualtat es tindrà que b = xab + ypb.
Substituint ab=np resulta que b = xnp + ybp = (xn + yb)p.
Per tant, definint m = xn + yb ja es té el nombre que es buscava i queda demostrat que b és un múltiple de p.
Per a trobar els nombres x, y de la identitat de Bézout, es pot emprar l'Algorisme d'Euclides ampliat.