WikiDer > Euklids Lemma

Es Euklids Lemma ist eine Aussage über Teiler des Produkts zweier ganzer Zahlen. Das Lemma sagt: wenn von zwei ganzen Zahlen ein und b es Produktabteilbar ist durch die Primzahl p, ist p auf jeden Fall Teiler von einem der beiden, so oder von ein oder von b (oder beides). Formal:

${displaystyle forall ,a,bin mathbb {Z} :p { ext{prime}}land p|abimplies p|alor p|b.}$

Lemma bedeutet Hilfsstellung. Das Lemma wird im Beweis von verwendet Hauptsatz der Arithmetik benutzt. Das Lemma ist nach dem griechischen Mathematiker Euklid von Alexandria, ca. 265 - 200 v. Chr., erwähnt.

Beweise

Annehmen ein nicht durch p geteilt werden, damit die größter gemeinsamer Teiler von ein und p gleich 1:

${Displaystil-Operatorname {ggd} (a,p)=1}$.

Laut der Satz von Bachet-Bézout gibt es ganze Zahlen? X und ja so dass:

${displaystyle xp ya=1}$.

Multiplikation beider Seiten mit b liefert

${displaystyle xpb yab=b}$.

weil ab durch p geteilt werden kann, ist auch yab durch p Teilen. Beide Produkte auf der linken Seite der Gleichung sind also p zu teilen, und ist auch b durch p Teilen.