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. +more 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. +more 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í).

Reference

Kategorie:Teorie čísel Kategorie:Matematické věty a důkazy