Eukleidovo lemma

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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í[editovat | editovat zdroj]

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

  • pokud dělí , tak dělí nebo
  • pokud dělí a nedělí , pak dělí
  • pokud nedělí ani , pak nedělí ani

Důkaz[editovat | editovat zdroj]

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

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

Prvočíslo zjevně dělí první sčítanec i druhý sčítanec, proto musí dělit i jejich součet, jímž je číslo .

Varianty[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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