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^[1]) 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 ${\displaystyle a}$ a ${\displaystyle b}$ celá čísla a ${\displaystyle p}$ je prvočíslo. Následující tvrzení jsou pak ekvivalentní:

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

Důkaz

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

${\displaystyle px+ay=1}$

Vynásobíme-li tuto rovnost číslem ${\displaystyle b}$, máme

${\displaystyle bpx+bay=b}$

Prvočíslo ${\displaystyle p}$ zjevně dělí první sčítanec i druhý sčítanec (${\displaystyle ba=ab}$, ${\displaystyle p}$ dělí ${\displaystyle ab}$), proto musí dělit i jejich součet, jímž je číslo ${\displaystyle 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í).

Reference