Vés al contingut

Lema d'Euclides

De la Viquipèdia, l'enciclopèdia lliure

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.

Vegeu també

[modifica]