|
Lema d'EuclidesEn 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ó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. Vegeu també |