Lema d'Euclides

Enunciat

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

Demostració

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ú 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:

$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)