Vés al contingut

Lema d'Euclides

De Viki.cat

Enunciat

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


Demostració

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

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

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

<math>1=x*a + y*p</math>

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

<math>b=x*a*b + y*a*p</math>

i com que <math>a*b=n*p</math>

substituint resulta que

<math>b=x*n*p+y*a*p</math>

i per tant

<math>b=(x*n + y*a)*p</math>

Amb lo que fent <math>n' = x*n + y*a</math> 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ú de 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:

<math>a=b*c+r</math>

Per tant

<math>r=a-b*c</math>

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

<math>r=nd + n'*d*c = (n+n'*c)*d</math> 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é:

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

Ara dividint p entre <math>r_1</math> es té:

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

A partir d'aquí es continua dividint:

<math>r_1 = q_3 * r_2 + r_3 \Rightarrow r_3 = r_1 - q_3 * r_2</math>

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

<math>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}</math>

<math>r_{i-2} = q_i * r_{i-1} + r_i</math>

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

D'aquí resulta que:

<math>1 = r_{i-3} - q_{i-1} * r_{i-2}</math>

Substituint <math>r_i-2</math>, <math>r_i-1</math>,... <math>r_1</math> pels valor trobats, al final queda:

<math>1= x*a+y*p</math> 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)