Eukleidovo lemma

Z Multimediaexpo.cz

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.

Obsah 1 Znění 2 Důkaz 3 Varianty 4 Reference

Znění

Lemma lze vyslovit v několika podobách. Nechť jsou \(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í).

Reference

1. ↑ Eukleidovy základy, VII. kniha, 30. postulát [online]. [cit. 2013-01-29]. Dostupné online. (starořecky, anglicky) 

Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii