Lema d'Euclides

De Viquipèdia

[edita] Enunciat

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

[edita] 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 = n d + 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)