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

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, proto musí dělit i jejich součet, jímž je číslo b.

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)