Euklidy lemma - Euclids lemma - Wikipedia

v teorie čísel, Euklidovo lemma je lemma který zachycuje základní vlastnost prvočísla, a to:^{[poznámka 1]}

Například pokud p = 19, A = 133, b = 143, pak ab = 133 × 143 = 19019, a protože je to dělitelné 19, lemma znamená, že jeden nebo oba z 133 nebo 143 musí být také. Ve skutečnosti, 133 = 19 × 7.

Přirozeně, pokud předpoklad lemmatu neplatí, tj. p je složené číslo, jeho důsledek může být pravdivý nebo nepravdivý. Například v případě p = 10, A = 4, b = 15, složené číslo 10 rozdělí ab = 4 × 15 = 60, ale 10 nerozdělí ani 4, ani 15.

Tato vlastnost je klíčem v dokladu o základní teorém aritmetiky.^{[poznámka 2]} Používá se k definování hlavní prvky, zobecnění prvočísel na libovolné komutativní prsteny. Euklidova lemma to ukazuje v celých číslech neredukovatelné prvky jsou také prvočísly. Důkaz používá indukce neplatí to tedy pro všechny integrální domény.

Formulace

Nechat ${ displaystyle p}$ být prvočíslo, a předpokládejme ${ displaystyle p}$ rozdělí součin dvou celých čísel ${ displaystyle a}$ a ${ displaystyle b}$. (V symbolech je to napsáno ${ displaystyle p mid ab}$. Jeho negace, ${ displaystyle p}$ nedělí ${ displaystyle ab}$ je psáno ${ displaystyle p nmid ab}$.) Pak ${ displaystyle p mid a}$ nebo ${ displaystyle p mid b}$ (nebo oboje). Ekvivalent prohlášení jsou:

• Li ${ displaystyle p nmid a}$ a ${ displaystyle p nmid b}$, pak ${ displaystyle p nmid ab}$.
• Li ${ displaystyle p nmid a}$ a ${ displaystyle p mid ab}$, pak ${ displaystyle p mid b}$.

Euklidovo lemma lze zobecnit z prvočísel na libovolná celá čísla:

Toto je zobecnění, protože pokud ${ displaystyle n}$ je také prime

• ${ displaystyle n mid a}$ nebo
• ${ displaystyle n}$ je relativně nejlepší ${ displaystyle a}$. V této druhé možnosti ${ displaystyle n nmid a}$ tak ${ displaystyle n mid b}$.

Dějiny

Lemma se poprvé objevuje jako tvrzení 30 v knize VII z Euklid je Elementy. Je zahrnuta prakticky v každé knize, která pojednává o základní teorii čísel.^{[4][5][6][7][8]}

Zevšeobecnění lemmatu na celá čísla se objevilo v Jean Prestet učebnice Nouveaux Elémens de Mathématiques v roce 1681.^[9]

v Carl Friedrich Gauss pojednání Disquisitiones Arithmeticae, výrok lemmatu je Euklidův Propozice 14 (Sekce 2), kterou používá k prokázání jedinečnosti produktu rozkladu hlavních faktorů celého čísla (Věta 16), přičemž připouští existenci jako „zjevnou“. Z této existence a jedinečnosti pak odvodí zobecnění prvočísel na celá čísla.^[10] Z tohoto důvodu se zobecnění Euklidova lematu někdy označuje jako Gaussovo lema, ale někteří věří, že toto použití je nesprávné^[11] kvůli záměně s Gaussovo lema o kvadratických zbytcích.

Důkaz

Důkaz pomocí Bézoutova lemmatu

Obvyklý důkaz zahrnuje další zvané lemma Bézoutova identita.^[12] To říká, že pokud X a y jsou relativně primární celá čísla (tj. nesdílejí žádné společné dělitele kromě 1 a -1) existují celá čísla r a s takhle

${ displaystyle rx + sy = 1.}$

Nechat A a n být relativně nejlepší a předpokládat, že n|ab. Podle Bézoutovy identity existují r a s tvorba

${ displaystyle rn + sa = 1.}$

Vynásobte obě strany b:

${ displaystyle rnb + sab = b.}$

První člen nalevo je dělitelný na druhý člen je dělitelný ab, což je hypotéza dělitelná n. Proto jejich součet, b, je také dělitelné n. Toto je zobecnění výše uvedeného Euklidova lematu.

Důkaz prvků

Euklidovo lemma je prokázáno v Proposition 30 v knize VII z Euklidova Elementy. Původní důkaz je těžké pochopit tak, jak je, takže citujeme komentář z Euclid (1956 319 až 332).

Tvrzení 19

Pokud jsou čtyři čísla proporcionální, počet vytvořený z prvního a čtvrtého se rovná počtu vytvořenému z druhého a třetího; a pokud se počet vytvořený z prvního a čtvrtého čísla rovná počtu vytvořenému z druhého a třetího, jsou čtyři čísla proporcionální.^{[Poznámka 3]}

Návrh 20.

Nejmenší počet těch, které mají stejný poměr, měří ty, které mají stejný poměr stejný početkrát - čím větší, tím větší a menší, tím méně.^{[poznámka 4]}

Tvrzení 21

Čísla jsou navzájem nejmenší z těch, která mají stejný poměr.^{[poznámka 5]}

Tvrzení 29.

Jakékoli prvočíslo je prvočíslo jakéhokoli čísla, které neměřuje.^{[poznámka 6]}

Návrh 30.

Pokud dvě čísla vzájemným vynásobením vytvoří stejné číslo a jakékoli prvočíslo měří produkt, měří také jedno z původních čísel.^{[poznámka 7]}

Důkaz 30

Li C, prvočíslo, míra ab, C opatření A nebo b.
Předpokládat C neměřuje A.
Proto C, A jsou si navzájem připraveni. ［VII. 29 ］
Předpokládat ab＝mc.
Proto C : A ＝ b : m. ［VII. 19 ］
Tedy ［VII. 20, 21 ］ b＝nc, kde n je celé číslo.
Proto C opatření b.
Podobně, pokud C neměřuje b, C opatření A.
Proto C měří jedno nebo druhé ze dvou čísel A, b.
Q.E.D.^[18]

Viz také

Poznámky pod čarou

Poznámky

Citace

Reference

• Bajnok, Béla (2013), Pozvánka na abstraktní matematiku, Pregraduální texty z matematiky Springer, ISBN  978-1-4614-6636-9.
• Euklid (1956), Třináct knih elementů, Sv. 2 (Knihy III-IX), přeložil Heath, Thomas Malý Publikace Dover, ISBN  978-0-486-60089-5- sv. 2
• Euklid (1994), Les Éléments, obchod, komentáře a poznámky (francouzsky), 2, přeložil Vitrac, Bernard, str. 338–339, ISBN  2-13-045568-9
• Gauss, Carl Friedrich (2001), Disquisitiones Arithmeticae, přeložil Clarke, Arthur A. (druhý, opravené vydání), New Haven, CT: Yale University Press, ISBN  978-0-300-09473-2
• Gauss, Carl Friedrich (1981), Untersuchungen uber hohere Arithmetik [Vyšetřování na vyšší aritmetice], překládal Maser, = H. (druhé vydání), New York: Chelsea, ISBN  978-0-8284-0191-3
• Hardy, G. H.; Wright, E. M.; Wiles, A. J. (2008-09-15), Úvod do teorie čísel (6. vydání), Oxford: Oxford University Press, ISBN  978-0-19-921986-5
• Irsko, Kenneth; Rosen, Michael (2010), Klasický úvod do moderní teorie čísel (Druhé vydání), New York: Springer, ISBN  978-1-4419-3094-1
• Joyner, David; Kreminski, Richard; Turisco, Joann (2004), Aplikovaná abstraktní algebra, JHU Press, ISBN  978-0-8018-7822-0.
• Landau, Edmund; Goodman, J. E. (překladatel do angličtiny) (1999), Základní teorie čísel (2. vyd.), Providence, Rhode Island: American Mathematical Society, ISBN  978-0-821-82004-9
• Martin, G. E. (2012), Základy geometrie a neeuklidovské roviny, Vysokoškolské texty z matematiky, Springer, ISBN  978-1-4612-5725-7.
• Riesel, Hans (1994), Prvočísla a počítačové metody pro faktorizaci (2. vyd.), Boston: Birkhäuser, ISBN  978-0-8176-3743-9.

externí odkazy

• Weisstein, Eric W. „Euklidovo lemma“. MathWorld.