Evklidova lema

Evklidova lema je v osnovni teoriji števil pomembna lema, ki se nanaša na deljivost in praštevila. V najpreprostejši obliki pravi, da praštevilo, ki deli (brez ostanka) produkt dveh celih števil, mora biti enemu od njiju delitelj. To ključno dejstvo nepričakovano zahteva spretni dokaz (s pomočjo Bézoutove enakosti) in je potreben korak pri standardnem dokazu osnovnega izreka aritmetike.

Evklidova lema, znana tudi kot Evklidov prvi izrek, se je pojavila kot trditev 30 v sedmi knjigi Evklidovih Elementov.

V sodobni matematiki se Evklidova lema večkrat rabi v naslednji posplošitvi: če n | ab in sta si n in a tuji, potem n | b. Ta trditev se prevede na Evklidovo trditev 30, če je n praštevilo.

Dokaz Evklidove leme

Standardni dokaz Evklidove leme uporablja Bézoutovo enakost. Ta pravi, da za dve tuji celi števili x in  y obstajata takšni celi števili r in s, da velja linearna diofantska enačba:

$rx+sy=1\!\,.$

Predpostavi se, da je p prafaktor produkta ab, in ni prafaktor a. Tako morata biti p in a tuji, in s tem obstajata takšni celi števili r in s, da velja:

$rp+sa=1\!\,.$

Če se pomnoži enačbo z b, se dobi:

$(rb)p+s(ab)=b\!\,.$

Prvi člen na levi strani je očitno mnogokratnik p. Ker p deli ab, je tudi drugi člen na levi strani mnogokratnik p. Odtod sledi, da je b mnogokratnik p, in p deli b. Tako je p vedno ali delitelj a ali delitelj b. Q.E.D.

S skoraj enakim dokazom je moč dokazati splošnejšo obliko Evklidove leme, kjer se p nadomesti s celim številom n.

Zgled

Če je število n mnogokratnik praštevila p in n = ab, mora biti vsaj eno od števil a ali b mnogokratnik p. Na primer:

$n=42\!\,,$

$p=7\!\,$

in

$n=14\cdot 3\!\,.$

Potem velja:

$7x=14\!\,$

ali:

$7x=3\!\,.$

V tem zgledu očitno 7 deli 14 (x = 2).

Glej tudi

• Evklidov algoritem