Eukleidovo lemma

Eukleidovo lemma je lemma v aritmetice a v teorii čísel, které říká, že pokud je nějaké prvočíslo dělitelem součinu celých čísel, pak dělí i nějaký z činitelů. Toto tvrzení se poprvé objevuje již v Eukleidových Základech (kniha VII, 30. postulát) a používá se například v důkaze Základní věty aritmetiky.

Znění

Lemma lze vyslovit v několika podobách. Nechť jsou-li $a$ a $b$ celá čísla a $p$ je prvočíslo. Následující tvrzení jsou pak ekvivalentní:

• pokud $p$ dělí $ab$, tak $p$ dělí $a$ nebo $b$
• pokud $p$ dělí $ab$ a $p$ nedělí $a$, pak $p$ dělí $b$
• pokud $p$ nedělí $a$ ani $b$, pak nedělí ani $ab$

Důkaz

Jednoduchý důkaz Eukleidova lemmatu je možný pomocí Bézoutovy rovnosti. Předpokládejme, že $p$ dělí $ab$ a nedělí $a$. Bézoutova rovnost nám pro libovolná dvě nesoudělná čísla, tedy například i pro prvočíslo $p$ a jím nedělitelné číslo $a$, zaručuje existenci $x$ a $y$ takových, že:

$px+ay=1$

Vynásobíme-li tuto rovnost číslem $b$, máme

$bpx+bay=b$

Prvočíslo $p$ zjevně dělí první sčítanec i druhý sčítanec ($ba=ab$, $p$ dělí $ab$), proto musí dělit i jejich součet, jímž je číslo $b$.

Varianty

Eukleidovo lemma neplatí pouze v celých číslech, ale platí také v jiných algebraických strukturách, v kterých funguje Eukleidův algoritmus (jenž konstruktivně zaručuje Bézoutovu rovnost), tedy v Eukleidovských oborech. Existence Eukleidova algoritmu ovšem není nutnou podmínkou, Eukleidovo lemma platí i v oborech hlavních ideálů (v kterých také pro libovolné nesoudělné prvky existuje Bézoutova rovnost, nicméně Eukleidův algoritmus v nich fungovat nemusí).