Lemma vum Euklid

De Lemma vum Euklid ass e Resultat aus der Zuelentheorie. E seet, datt all natierlech Zuel $n>1$ vun enger Primzuel gedeelt gëtt.

Beweis

De Beweis gëtt mam Prinzip gefouert, datt en Ensemble vun natierlechen Zuelen, deen net eidel ass, ëmmer e klengstent Element enthält. Elo ass eng natierlech Zuel $n>1$ entweder eng Primzuel (d.h. mer si fäerdeg mam Beweis, well $n$ jo säin eegenen Deeler ass), oder se ass zesummegesat, d.h. et gtt eng natierlech Zuel $1<m<n$, déi $n$ deelt. Faasse mer alleguerten déi natierlech Zuelen zesummen, déi dës lescht Bedingung erfëllen, dann kreie mer den net eidelen Ensemble

$D:=\{m\in\mathbb{N}: 1<m<n, m|n\}$.

Dësen huet also e kléngstent Element, d.h. et gëtt eng natierlech Zuel $k\in D$, déi méi kleng wéi all déi aner Elementer vun $D$ ass. Da muss $k$ eng Primzuel sinn, well wa $k$ zesummegesat wier, da géif jo nees eng natierlech Zuel $1<l<k$ existéieren, déi $k$ deelt, an opgrond vun der Transitivitéit vun der Deelbarkeet (cf. Deeler) misst $l$ och $n$ deelen, also en Element vun $D$ sinn. Dat steet awer am Widdersproch dozou, dat $k$ dat klengsten Element vun $D$ ass. Dat beweist de Lemma.