Základní věta o aritmetice - Fundamental theorem of arithmetic

Jedinečná faktorizační věta byla prokázána Gauss s jeho knihou z roku 1801 Disquisitiones Arithmeticae.^[1] V této knize Gauss použil základní teorém k prokázání zákon kvadratické vzájemnosti.^[2]

v teorie čísel, základní teorém aritmetiky, také nazývaný jedinečná faktorizační věta nebo věta o jedinečné prvočíselné faktorizaci, uvádí, že každý celé číslo větší než 1^[3] buď je prvočíslo nebo může být reprezentován jako produkt prvočísel a navíc je toto zobrazení jedinečné, až do (kromě) pořadí faktorů.^[4][5][6] Například,

${ displaystyle 1200 = 2 ^ {4} cdot 3 cdot 5 ^ {2} = (2 cdot 2 cdot 2 cdot 2) cdot 3 cdot (5 cdot 5) = 5 cdot 2 cdot 5 cdot 2 cdot 3 cdot 2 cdot 2 = ldots}$

Věta říká pro tento příklad dvě věci: zaprvé, že 1200 umět být reprezentován jako produkt prvočísel, a za druhé, že bez ohledu na to, jak se to dělá, v produktu budou vždy přesně čtyři 2s, jedna 3, dvě 5s a žádná další prvočísla.

Nutný je požadavek, aby faktory byly prvočíselné: faktorizace obsahující složená čísla nemusí být jedinečné (například ${ displaystyle 12 = 2 cdot 6 = 3 cdot 4}$).

Tato věta je jednou z hlavních důvody, proč 1 není považován za prvočíslo: kdyby 1 byla prvočíslo, potom by faktorizace na prvočísla nebyla jedinečná; například, ${ displaystyle 2 = 2 cdot 1 = 2 cdot 1 cdot 1 = ldots}$

Euklidova původní verze

Kniha VII, propozice 30, 31 a 32 a kniha IX, propozice 14 z Euklid je Elementy jsou v zásadě tvrzením a důkazem základní věty.

Pokud dvě čísla vzájemným vynásobením vytvoří somenumber a jakékoli prvočíslo měří produkt, změří se také jedno z původních čísel.

— Euklid, Kniha Prvky VII, Tvrzení 30

(V moderní terminologii: pokud je prvočíslo p rozděluje produkt ab, pak p rozděluje buď A nebo b nebo obojí.) Návrh 30 se označuje jako Euklidovo lemma, a je klíčem v důkazu základní věty o aritmetice.

Jakékoli složené číslo se měří nějakým prvočíslem.

— Euklid, Kniha Prvky VII, Tvrzení 31

(V moderní terminologii: každé celé číslo větší než jedno je rovnoměrně rozděleno nějakým prvočíslem.) Tvrzení 31 dokazuje přímo nekonečný sestup.

Jakékoli číslo je buď prvočíslo, nebo se měří nějakým prvočíslem.

— Euklid, Kniha prvků VII, Návrh 32

Návrh 32 je odvozen z návrhu 31 a dokazuje, že je možný rozklad.

Pokud je číslo nejméně, které se měří prvočísly, nebude měřeno jiným prvočíslem kromě těch, které jej původně měřily.

— Euklid, Kniha prvků IX, Tvrzení 14

(V moderní terminologii: a nejmenší společný násobek několika prvočísel není násobkem žádného jiného prvočísla.) Kniha IX, výrok 14 je odvozen z knihy VII, výrok 30, a částečně dokazuje, že rozklad je jedinečný - bod kriticky poznamenaný André Weil.^[7] Ve skutečnosti jsou v tomto návrhu všechny exponenty rovny jedné, takže pro obecný případ se nic neříká.

Článek 16 Gauss ' Disquisitiones Arithmeticae je brzy moderní prohlášení a důkaz zaměstnává modulární aritmetika.^[1]

Aplikace

Kanonické vyjádření kladného celého čísla

Každé kladné celé číslo n > 1 lze reprezentovat přesně jedním způsobem jako produkt hlavních sil:

${ displaystyle n = p_ {1} ^ {n_ {1}} p_ {2} ^ {n_ {2}} cdots p_ {k} ^ {n_ {k}} = prod _ {i = 1} ^ {k} p_ {i} ^ {n_ {i}}}$

kde p₁ < p₂ < ... < p_k jsou prvočísla a n_i jsou kladná celá čísla. Tato reprezentace je běžně rozšířena na všechna kladná celá čísla, včetně 1, podle konvence, kterou prázdný produkt se rovná 1 (prázdný produkt odpovídá k = 0).

Tato reprezentace se nazývá kanonická reprezentace^[8] z n, nebo standardní forma^[9][10] z n. Například,

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

Faktory p⁰ = 1 může být vložen beze změny hodnoty n (například 1000 = 2³×3⁰×5³). Ve skutečnosti lze každé kladné celé číslo jednoznačně reprezentovat jako nekonečný produkt převzal všechna kladná prvočísla:

${ displaystyle n = 2 ^ {n_ {1}} 3 ^ {n_ {2}} 5 ^ {n_ {3}} 7 ^ {n_ {4}} cdots = prod _ {i = 1} ^ { infty} p_ {i} ^ {n_ {i}},}$

kde konečný počet n_i jsou kladná celá čísla a zbytek je nula. Povolení záporných exponentů poskytuje kanonickou formu pro kladné racionální čísla.

Aritmetické operace

Kanonická znázornění produktu, největší společný dělitel (GCD) a nejmenší společný násobek (LCM) dvou čísel A a b lze vyjádřit jednoduše kanonickými reprezentacemi A a b oni sami:

${ displaystyle { begin {alignedat} {2} a cdot b & {} = {} 2 ^ {a_ {1} + b_ {1}} 3 ^ {a_ {2} + b_ {2}} 5 ^ { a_ {3} + b_ {3}} 7 ^ {a_ {4} + b_ {4}} cdots && {} = {} prod p_ {i} ^ {a_ {i} + b_ {i}}, gcd (a, b) & {} = {} 2 ^ { min (a_ {1}, b_ {1})} 3 ^ { min (a_ {2}, b_ {2})} 5 ^ { min (a_ {3}, b_ {3})} 7 ^ { min (a_ {4}, b_ {4})} cdots && {} = {} prod p_ {i} ^ { min (a_ {i}, b_ {i})}, operatorname {lcm} (a, b) & {} = {} 2 ^ { max (a_ {1}, b_ {1})} 3 ^ { max (a_ {2}, b_ {2})} 5 ^ { max (a_ {3}, b_ {3})} 7 ^ { max (a_ {4}, b_ {4})} cdots && {} = {} prod p_ {i} ^ { max (a_ {i}, b_ {i})}. end {alignedat}}}$

Nicméně, celočíselná faktorizace, zejména velkých čísel, je mnohem obtížnější než výpočetní produkty, GCD nebo LCM. Takže tyto vzorce mají v praxi omezené použití.

Aritmetické funkce

Mnoho aritmetických funkcí je definováno pomocí kanonické reprezentace. Zejména hodnoty přísada a multiplikativní funkce jsou určovány jejich hodnotami na mocninách prvočísel.

Důkaz

Důkaz používá Euklidovo lemma (Elementy VII, 30): Pokud je prvočíslo p rozděluje produkt ab dvou celých čísel A a b, pak p musí rozdělit alespoň jedno z těchto celých čísel A a b.

Existence

Musí se ukázat, že každé celé číslo větší než 1 je buď prvočíslo, nebo součin prvočísel. Nejprve je 2 prvočíslo. Pak, tím silná indukce, předpokládejme, že to platí pro všechna čísla větší než 1 a menší než n. Li n je prime, není už co dokazovat. Jinak existují celá čísla A a b, kde n = ab, a 1 < A ≤ b < n. Podle indukční hypotézy A = p₁p₂...p_j a b = q₁q₂...q_k jsou produkty prvočísel. Ale pak n = ab = p₁p₂...p_jq₁q₂...q_k je produkt prvočísel.

Jedinečnost

Předpokládejme, že naopak existuje celé číslo, které má dvě odlišné primární faktorizace. Nechat n být nejméně takové celé číslo a psát n = p₁ p₂ ... p_j = q₁ q₂ ... q_k, kde každý p_i a q_i je hlavní. (Poznámka j a k jsou oba minimálně 2.) Vidíme p₁ rozděluje q₁ q₂ ... q_k, tak p₁ rozděluje některé q_i podle Euklidova lematu. Řekněme bez ztráty obecnosti p₁ rozděluje q₁. Od té doby p₁ a q₁ jsou oba hlavní, z toho vyplývá p₁ = q₁. Návrat k našim faktorizacím n, můžeme tyto dvě podmínky na závěr zrušit p₂ ... p_j = q₂ ... q_k. Nyní máme dvě odlišné primární faktorizace nějakého celého čísla striktně menšího než n, což je v rozporu s minimem n.

Základní důkaz jedinečnosti

Základní teorém aritmetiky lze také dokázat bez použití Euklidova lematu, a to následovně:

Předpokládat, že s > 1 je nejmenší kladné celé číslo, které je součinem prvočísel dvěma různými způsoby. Li s byly prvotřídní, pak by to činilo jedinečně jako samo, tak s není prvočíslo a v každé faktorizaci faktoru musí být alespoň dvě prvočísla s:

${ displaystyle { begin {aligned} s & = p_ {1} p_ {2} cdots p_ {m} & = q_ {1} q_ {2} cdots q_ {n}. end {aligned}} }$

Jestli nějaký p_i = q_j poté zrušením s/p_i = s/q_j by bylo další kladné celé číslo, odlišné od s, které je větší než 1 a má také dvě odlišné faktorizace. Ale s/p_i je menší než s, význam s by ve skutečnosti nebylo nejmenší celé číslo. Proto každý p_i musí být odlišné od každého q_j.

Bez ztráty obecnosti, vezměte si p₁ < q₁ (pokud tomu tak již není, přepněte p a q označení.) Zvažte

${ displaystyle t = (q_ {1} -p_ {1}) (q_ {2} cdots q_ {n}),}$

a všimněte si, že 1 < q₂ ≤ t < s. Proto t musí mít jedinečnou primární faktorizaci. Podle přeskupení vidíme,

${ displaystyle { begin {aligned} t & = q_ {1} (q_ {2} cdots q_ {n}) - p_ {1} (q_ {2} cdots q_ {n}) & = s- p_ {1} (q_ {2} cdots q_ {n}) & = p_ {1} ((p_ {2} cdots p_ {m}) - (q_ {2} cdots q_ {n}) ). end {zarovnáno}}}$

Tady u = ((p₂ ... p_m) - (q₂ ... q_n)) je kladný, protože pokud by byl záporný nebo nulový, pak by byl jeho produkt s p₁, ale tento produkt se rovná t což je pozitivní. Tak u je buď 1 nebo započítává do prvočísel. V obou případech t = p₁u poskytuje primární faktorizaci ve výši t, o kterém víme, že je jedinečný, takže p₁ se objeví v primární faktorizaci t.

Pokud (q₁ - p₁) se rovnal 1, pak primární faktorizace t bude vše q 's, což by vylučovalo p₁ od objevení. Tím pádem (q₁ - p₁) není 1, ale je pozitivní, takže se rozdělí na prvočísla: (q₁ - p₁) = (r₁ ... r_h). Tím se získá primární faktorizace ve výši

${ displaystyle t = (r_ {1} cdots r_ {h}) (q_ {2} cdots q_ {n}),}$

o kterém víme, že je jedinečný. Nyní, p₁ se objeví v primární faktorizaci t, a to se nerovná žádnému q, takže to musí být jeden z r 's. To znamená p₁ je faktorem (q₁ - p₁), takže existuje kladné celé číslo k takhle p₁k = (q₁ - p₁), a proto

${ displaystyle p_ {1} (k + 1) = q_ {1}.}$

Ale to znamená q₁ má správnou faktorizaci, takže nejde o prvočíslo. Tento rozpor to ukazuje s ve skutečnosti nemá dvě různé primární faktorizace. Výsledkem je, že neexistuje žádné nejmenší kladné celé číslo s více prvočíselnými faktorizacemi, proto jsou všechna kladná celá čísla větší než 1 faktor jedinečně do prvočísel.

Zobecnění

První zobecnění věty se nachází v Gaussově druhé monografii (1832) dvojkvadratická vzájemnost. Tento článek představil to, co se nyní nazývá prsten z Gaussova celá čísla soubor všech komplexní čísla A + bi kde A a b jsou celá čísla. Nyní je označen ${ displaystyle mathbb {Z} [i].}$ Ukázal, že tento prsten má čtyři jednotky ± 1 a ±i, že nenulová, nejednotná čísla spadají do dvou tříd, prvočísel a kompozitů, a že (kromě objednávky) mají kompozity jedinečnou faktorizaci jako produkt prvočísel.^[11]

Podobně v roce 1844 při práci na kubická vzájemnost, Eisenstein představil prsten ${ displaystyle mathbb {Z} [ omega]}$, kde ${ displaystyle omega = { frac {-1 + { sqrt {-3}}} {2}},}$   ${ displaystyle omega ^ {3} = 1}$ je kostka kořen jednoty. To je prsten Eisensteinova celá čísla a dokázal, že má těch šest jednotek ${ displaystyle pm 1, pm omega, pm omega ^ {2}}$ a že má jedinečnou faktorizaci.

Bylo však také zjištěno, že ne vždy platí jedinečná faktorizace. Příklad uvádí ${ displaystyle mathbb {Z} [{ sqrt {-5}}]}$. V tomto kruhu jeden má^[12]

${ displaystyle 6 = 2 cdot 3 = (1 + { sqrt {-5}}) (1 - { sqrt {-5}}).}$

Příklady, jako je tento, způsobily úpravu pojmu „prime“. v ${ displaystyle mathbb {Z} [{ sqrt {-5}}]}$ lze dokázat, že pokud lze některý z výše uvedených faktorů představovat jako produkt, například 2 = ab, pak jeden z A nebo b musí být jednotka. Toto je tradiční definice „prime“. Lze také prokázat, že žádný z těchto faktorů nepodřídí Euklidovo lemma; například 2 nerozdělí ani jeden (1 + √−5) ani (1 - √−5), i když rozděluje jejich produkt 6. V algebraická teorie čísel 2 se volá neredukovatelné v ${ displaystyle mathbb {Z} [{ sqrt {-5}}]}$ (pouze dělitelné samostatně nebo jednotkou), ale ne primární v ${ displaystyle mathbb {Z} [{ sqrt {-5}}]}$ (pokud rozděluje produkt, musí rozdělit jeden z faktorů). Zmínka o ${ displaystyle mathbb {Z} [{ sqrt {-5}}]}$ je vyžadováno, protože 2 je primární a neredukovatelné ${ displaystyle mathbb {Z}.}$ Pomocí těchto definic lze dokázat, že v každém integrální doména prvočíslo musí být neredukovatelné. Euklidovo klasické lemma lze přeformulovat jako „v kruhu celých čísel ${ displaystyle mathbb {Z}}$ každá neredukovatelná je primární. “To platí také v ${ displaystyle mathbb {Z} [i]}$ a ${ displaystyle mathbb {Z} [ omega],}$ ale ne v ${ displaystyle mathbb {Z} [{ sqrt {-5}}].}$

Jsou nazývány prstence, ve kterých je faktorizace na neredukovatelné v podstatě jedinečná jedinečné faktorizační domény. Důležité příklady jsou polynomiální kroužky přes celá čísla nebo přes a pole, Euklidovské domény a hlavní ideální domény.

V roce 1843 Kummer představil koncept ideální číslo, který dále rozvinul Dedekind (1876) do moderní teorie ideály, speciální podmnožiny prstenů. Násobení je definováno pro ideály a jsou nazývány prsteny, ve kterých mají jedinečnou faktorizaci Dedekindovy domény.

Existuje verze jedinečná faktorizace pro ordinály, i když to vyžaduje několik dalších podmínek, aby byla zajištěna jedinečnost.

Viz také

• Faktorizace celého čísla - Rozklad celého čísla na produkt
• Prime podpis - Multiset prvočíselných exponentů v prvočíselné faktorizaci

Poznámky

Reference

The Disquisitiones Arithmeticae byl přeložen z latiny do angličtiny a němčiny. Německé vydání obsahuje všechny jeho práce o teorii čísel: všechny důkazy kvadratické reciprocity, stanovení znaménka Gaussovy sumy, vyšetřování biquadratické reciprocity a nepublikované poznámky.

• Gauss, Carl Friedrich; Clarke, Arthur A. (překladatel do angličtiny) (1986), Disquisitiones Arithemeticae (druhé, opravené vydání), New York: Springer, ISBN  978-0-387-96254-2
• Gauss, Carl Friedrich; Maser, H. (překladatel do němčiny) (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae a další články o teorii čísel) (druhé vydání), New York: Chelsea, ISBN  0-8284-0191-8

Dvě monografie Gauss publikované o dvojkvadratické vzájemnosti mají postupně očíslované oddíly: první obsahuje §§ 1–23 a druhá §§ 24–76. Poznámky pod čarou, které na ně odkazují, mají tvar „Gauss, BQ, § nPoznámky pod čarou odkazující na Disquisitiones Arithmeticae mají formu „Gauss, DA, čl. n".

• Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Komentář. Soc. regiae sci, Göttingen 6
• Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, Göttingen: Komentář. Soc. regiae sci, Göttingen 7

Ty jsou v Gaussově Werke, Sv. II, str. 65–92 a 93–148; Německé překlady jsou na str. 511–533 a 534–586 německého vydání Disquisitiones.

• Baker, Alan (1984), Stručný úvod do teorie čísel, Cambridge, Velká Británie: Cambridge University Press, ISBN  978-0-521-28654-1
• Euklid (1956), Třináct knih Prvků, 2 (knihy III-IX), přeložil Thomas Little Heath (Second Edition Unabridged ed.), New York: Doveru, ISBN  978-0-486-60089-5
• Hardy, G. H.; Wright, E. M. (2008) [1938]. Úvod do teorie čísel. Revidováno D. R. Heath-Brown a J. H. Silverman. Předmluva Andrew Wiles. (6. vydání). Oxford: Oxford University Press. ISBN  978-0-19-921986-5. PAN  2445243. Zbl  1159.11001.
• A. Kornilowicz; P. Rudnicki (2004), „Základní věta aritmetiky“, Formalizovaná matematika, 12 (2): 179–185
• Long, Calvin T. (1972), Základní úvod do teorie čísel (2. vyd.), Lexington: D. C. Heath and Company, LCCN  77-171950.
• Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970), Prvky teorie čísel, Englewoodské útesy: Prentice Hall, LCCN  77-81766.
• Riesel, Hans (1994), Prvočísla a počítačové metody pro faktorizaci (druhé vydání), Boston: Birkhäuser, ISBN  0-8176-3743-5
• Weil, André (2007) [1984]. Teorie čísel: Přístup v historii od Hammurapiho po Legendra. Moderní Birkhäuserova klasika. Boston, MA: Birkhäuser. ISBN  978-0-817-64565-6.
• Weisstein, Eric W. „Abnormal number“. MathWorld.
• Weisstein, Eric W. „Základní věta o aritmetice“. MathWorld.

externí odkazy

• Proč není zřejmá základní věta aritmetiky?
• GCD a základní věta aritmetiky na cut-the-uzel.
• PlanetMath: Důkaz základní věty o aritmetice
• Fermatův poslední teorémový blog: Jedinečná faktorizace, blog, který se věnuje historii Fermatova poslední věta z Diophantus Alexandrijský k důkazu Andrew Wiles.
• „Základní věta o aritmetice“ autor: Hector Zenil, Demonstrační projekt Wolfram, 2007.
• Špína, James. „1 a prvočísla“. Numberphile. Brady Haran.