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 Ensembel vun natierlechen Zuelen, deen net eidel ass, ëmmer e klengstent Element enthält. Elo ass eng natierlech Zuel $n>1$ entweeder 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 alleguer déi natierlech Zuelen zesummen, déi dës lescht Bedingung erfëllen, da kréie mer den net eidelen Ensembel

$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 klengst Element vun $D$ ass. Dat beweist de Lemma.