Lema d'Euclides

De Viquipèdia
Dreceres ràpides: navegació, cerca

Enunciat[modifica | modifica el codi]

El lema d'Euclides diu que si un nombre primer p divideix el producte a*b i no divideix a llavors divideix b.


Demostració[modifica | modifica el codi]

Si p divideix a*b vol dir que existeix un nombre enter n>1 tal que a*b=n*p

La demostració del lema d'Euclides es fa trobant un nombre enter n' tal que b=n' * p

El primer pas serà trobar dos nombres enters x e y tals que:

1=x*a + y*p

Un cop s'hagin trobat aquests dos nombres multiplicant per b els dos termes de la igualtat es tindrà que

b=x*a*b + y*a*p

i com que a*b=n*p

substituint resulta que

b=x*n*p+y*a*p

i per tant

b=(x*n + y*a)*p

Amb lo que fent n' = x*n + y*a ja es tindrà el nombre que es buscava i quedarà demostrat que b és múltiple de p.

Per a trobar els dos nombres x e y cal fixar-se que si un nombre és divisor comú d'uns altres dos, també ho és del residu. Això és evident: siguin a,b dos nombres, en dividir a entre b es troba el quocient q i el residu r i es pot expressar:

a=b*c+r

Per tant

r=a-b*c

Si un nombre d és divisor comú de a i de b vol dir que existeixen nombres n i n’ tals que a=n*d i b=n'*d, substituint resulta que;

r=nd + n'*d*c = (n+n'*c)*d per tant d també és divisor de r.

Aquesta idea és amb la que es basa l'Algorisme d'Euclides per a trobar el màxim comú denominador de dos nombres. Aquí es farà servir per a trobar els nombre x e y de forma que quedarà completada la demostració del lema.

Dividint a entre p es té:

a= q_1*p+r_1 \Rightarrow r_1=a-q_1*p (amb r_1 diferent de zero perquè p no divideix a)

Ara dividint p entre r_1 es té:

p=q_2*r_1+r_2 (amb r_2 diferent de zero perquè p és un nombre primer)

A partir d'aquí es continua dividint:

r_1 = q_3 * r_2 + r_3 \Rightarrow r_3 = r_1 - q_3 * r_2

Fins a trobar un r_i amb i>=3 que sigui zero:

r_{i-3} = q_{i-1} * r_{i-2} + r_{i-1} \Rightarrow r_{i-1} = r_{i-3} - q_{i-1} * r_{i-2}

r_{i-2} = q_i * r_{i-1} + r_i

Com que r_i = 0, r_i-1 és divisor comú de r_i-2, r_i-3,... r_2, r_1, a,p. Però p és un nombre primer, per tant l'únic divisor que té diferent de ell mateix és 1. Per tant r_i-1 = 1.

D'aquí resulta que:

1 = r_{i-3} - q_{i-1} * r_{i-2}

Substituint r_i-2, r_i-1,... r_1 pels valor trobats, al final queda:

1= x*a+y*p on x i y són els dos nombres sencers que es buscaven (un dels dos és negatiu però no hi ha cap problema perquè no cal que siguin positius)