Základní teorém aritmetiky

Základní teorém aritmetiky říká, že [1] [2]

každé přirozené číslo lze rozložit ( rozšířit ) ve tvaru $n>1$ ${\displaystyle n=p_{1}\cdot \ldots \cdot p_{k))$ ${\displaystyle p_{1},\ldots ,p_{k))$

Pokud se formálně shodneme na tom, že prázdný součin prázdné množiny čísel je roven 1, pak lze podmínku ve formulaci vynechat – pak pro jednotu implikuje rozklad prázdnou množinou prvočísel: [3] [ 4] . $n>1$ $1=1$

V důsledku toho může být každé přirozené číslo reprezentováno jako $n$

n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k)),

kde jsou prvočísla a nějaká přirozená čísla,

{\displaystyle p_{1}<p_{2}<\ldots <p_{k))

{\displaystyle d_{1},\ldots ,d_{k))

a jedinečným způsobem. Tato reprezentace čísla se nazývá jeho kanonická faktorizace . $n$

Důkaz

Podle metody indukce

Existence : dokážeme existenci rozkladu čísla na prvočinitele, pokud předpokládáme, že totéž již bylo prokázáno pro jakékoli jiné číslo menší než . Je-li prvočíslo, pak je existence dokázána. Jestliže je složené, pak to může být reprezentováno jako součin dvou čísel a , z nichž každé je větší než 1, ale menší než . Čísla a jsou buď prvočísla, nebo je lze rozložit na součin prvočísel (již dokázáno dříve). Dosazením jejich rozkladu na , získáme rozklad původního čísla na prvočísla. Existence je prokázána [5] . $n$ $n$ $n$ $n$ $A$ $b$ $n$ $A$ $b$ $n=a\cdot b$ $n$

Jedinečnost : U prvočísla je jednoznačnost zřejmá.

Pro složené číslo je myšlenkou důkazu použít metodu "protikladem" , jmenovitě je předložen předpoklad, že číslo má dvě různá rozšíření. Uvažujeme prvočísla a , která jsou nejmenší v prvním a druhém z těchto rozšíření, a dokážeme následující lemma: $p_{0}$ $q_{0}$

je-li rozklad čísla na prvočinitele jedinečný, pak musí být do tohoto rozkladu zahrnut každý prvočíslo. $m$ $m$

Dále uvažujeme číslo , které je zase přirozené číslo a které je menší než . Z induktivního předpokladu a výše uvedeného lemmatu vyplývá, že je dělitelem daného čísla, načež se podobně usuzuje, že první rozklad je dělitelný . Žádné prvočíslo se nemůže vyskytovat v obou rozkladech najednou, protože jinak by bylo možné je redukovat a získat různé rozklady na prvočinitele čísla menšího než . ${\displaystyle n-p_{0}\cdot q_{0))$ $n$ $p_{0}\cdot q_{0}$ $q_{0}$ $n$ $n$

Použití Euklidova algoritmu

Základní větu aritmetiky lze dokázat pomocí důsledků z Euklidova algoritmu [7] :

největší společný dělitel je největší společný dělitel a násobí se . $n\cdot a$ $n\cdot b$ $A$ $b$ $n$

Z tohoto důsledku lze dokázat Euklidovo lemma , které je také nezbytné pro důkaz věty:

jestliže je prvočíslo a součin dvou čísel je dělitelný , pak alespoň jeden z těchto dvou faktorů je dělitelný . $p$ $p$ $p$

Existence: Myšlenka za důkazem existence je dokázat lemma:

zvažte prvočíslo a součin . Pokud je dělitelná , ale není dělitelná , pak je dělitelná . $p$ $n\cdot a$ $n\cdot a$ $p$ $A$ $p$ $n$ $p$

Dále pomocí výše uvedeného lemmatu je číslo postupně rozloženo na prvočinitele za předpokladu, že jsou známi všichni prvočíslí dělitelé tohoto čísla.

Jedinečnost: nechť má číslo n dva různé rozklady na prvočísla:

n=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots =p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots

Protože je dělitelné , pak buď , nebo je dělitelné . Jestliže je dělitelné , pak , protože obě tato čísla jsou prvočísla. Pokud je dělitelné , pak pokračujeme v předchozí úvaze. Nakonec se ukáže, že jedno z čísel se rovná číslu , a proto se obě rozšíření čísla ve skutečnosti shodují. Tím je prokázána jednoznačnost rozkladu. $p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1}$ $p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1}$ $p_{1}$ $p'_{1}=p_{1}$ $p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1},p'_{2},p'_{3},\ldots$ $p_{1}$

Historie

Premisy základní věty aritmetiky mají svůj původ ve starověkém Řecku . Navzdory skutečnosti, že ve starověké řecké matematice se základní teorém aritmetiky v moderní formulaci nevyskytuje, v „ Principech “ ( jiné řecké Στοιχεῖα ) má Euclid ekvivalentní věty. Po Euklidovi mnoho matematiků v průběhu staletí přispělo k důkazu základní věty aritmetiky a citovali ve svých dílech významově blízká tvrzení, mezi tyto vědce patří Kamal ad-Din al-Farisi , J. Preste , L Euler , A. Legendre [8] . První přesnou formulaci základní věty aritmetiky a její důkaz uvádí K. Gauss v knize " Aritmetická vyšetřování " ( lat. Disquisitiones Arithmeticae ), publikované v roce 1801 [9] . Od té doby se objevilo mnoho různých nových důkazů teorému, které spolu soupeřily v kráse a originalitě [8] .

Euklides (3. století př. n. l.)

Euclid vyložil v Elementech důležité základy pro teorii čísel, včetně základního teorému aritmetiky. Tři věty, které jsou svým významem velmi blízké Základní větě aritmetiky, lze nalézt v Knize VII a IX, jmenovitě Tvrzení 30 z Knihy VII, nejlépe známé jako Euklidovo lemma , Tvrzení 31 z Knihy VII a Tvrzení 14 z Knihy IX. Níže jsou jejich verze v překladu Morduchaie-Boltovského :

VII.30:

Jestliže dvě čísla, která se navzájem násobí, něco vytvoří a to, co z nich vznikne, je měřeno nějakým prvním číslem, pak (to druhé) bude měřit také jedno z původních [10]

VII.31:

Každé složené číslo se měří nějakým prvním číslem [11]

IX.14:

Pokud je číslo nejmenší měřitelné (dané) prvními čísly, pak jej nelze měřit žádným jiným prvočíslem, kromě těch, kteří (to) původně měřili [12]

V současnosti[ co? ] čas je důkaz základní věty aritmetiky odvozen z výroků VII.30 a VII.31, ale Eukleidés tento důkaz ve svých spisech nepředložil. Tvrzení IX.14 je zase dost podobné tvrzení o jedinečnosti rozkladu na prvočísla, ale ukázalo se, že toto tvrzení nepokrývá všechny možné případy – například když se objeví alespoň jedna druhá mocnina prvočísla při rozkladu na prvočinitele [13] [14] .

Al-Farisi (XIV století)

Slavný perský vědec Kamal ad-Din al-Farisi udělal významný krok vpřed ve studiu základní věty aritmetiky. Ve svém díle Memorandum for friends on the proof of amicability prokázal existenci faktorizace na prvočinitele a poskytl potřebné informace k prokázání jedinečnosti tohoto rozkladu . Kamal al-Farisi se však nejvíce zajímal o sestavení vlastního důkazu pro větu Sabit ibn Kurra o hledání přátelských čísel - a al-Farisi se nesnažil dokázat základní větu aritmetiky, ale hledal všechny dělitele aritmetického teorému. složené číslo [15] . Pečlivě zkoumal rozklad čísel a formuloval a dokázal tvrzení, které se ve skutečnosti ukázalo jako důkaz existence rozkladu přirozeného čísla na prvočinitele.

V překladu zní jeho prohlášení asi takto:

Každé složené číslo lze rozložit na konečný počet prvočinitelů, jichž je součinem.

V prohlášení 9 al-Farisi formuloval princip pro určování všech dělitelů složeného čísla: to bylo přesně to, co potřeboval, aby dokázal Ibn Qurrovu větu. Překlad zní takto:

Pokud se složené číslo rozloží na prvočinitele jako , pak nemá dělitele kromě a a součin každého z nich s každým, součin trojic atd. až po součin všech prvků bez jednoho. $A$ $a=b\cdot c\cdot d\cdot h\cdot \ldots \cdot k\cdot l$ $A$ $jeden$ $b,c,d,...,k,l$

Již ze samotného znění prohlášení lze usoudit, že al-Farisi věděl o jedinečnosti rozkladu na prvočinitele. Kromě toho jsou všechna tvrzení a fakta uvedená vědcem k prokázání tohoto tvrzení nezbytným souborem pro prokázání jedinečnosti v hlavní větě aritmetiky.

Jean Preste (17. století)

Výsledky publikované Jeanem Prestem v knize Elements de Mathématiques (1675) potvrzují, že prvočíselná faktorizace nebyla v té době považována za něco zajímavého samo o sobě, ale za užitečnou aplikaci – prostředek k nalezení dělitelů daného čísla. . Preste neformuloval ani existenci, ani jednoznačnost rozkladu a nejvíce pozornosti věnoval samotnému hledání dělitelů čísla [16] . Navzdory tomu Preste, stejně jako al-Farisi, poskytl všechny potřebné informace k prokázání jedinečnosti faktorizace prostřednictvím svého Důsledku IX, který sám o sobě lze považovat za ekvivalent jedinečnosti faktorizace.

Důsledek IX:

Pokud jsou čísla a prvočísla, pak každý dělitel čísla je buď , nebo , nebo , nebo jeden ze součinů těchto tří čísel podle . To je jeden ze šesti: . $A$ $b$ $a\cdot a\cdot b$ $A$ $a^2$ $jeden$ $b$ $1,a,a\cdot a,1\cdot b,a\cdot b,a\cdot a\cdot b$

Euler a Legendre (18. století)

V The Complete Guide to Algebra ( Německy: Vollstandige Einleitung zur Algebra ) publikoval Leonhard Euler výsledky podobné těm, které měli jeho předchůdci. Zformuloval existenci faktorizace čísla na prvočinitele a s vynecháním některých detailů to poskytl částečným důkazem v odstavci 41 kapitoly IV z první části prvního oddílu knihy.

Jeho překlad je následující:

Všechna složená čísla, která lze faktorizovat, jsou reprezentována součinem prvočísel; to znamená, že všechny jejich faktory jsou prvočísla. Pokud je totiž nalezen faktor, který není prvočíslem, může být vždy rozložen a reprezentován dvěma nebo více prvočísly.

Euler neformuloval věty o jedinečnosti rozkladu, ale navrhl podobné tvrzení, které ponechal bez důkazu, v oddíle 65 kapitoly IV prvního oddílu prvního dílu. Tam Euler implicitně vysvětluje, že rozklad čísla na prvočinitele je jedinečný, když říká, že všechny dělitele čísla lze nalézt tak, že znáte prvočinitele z rozkladu daného čísla [17] . Tuto položku lze tedy považovat za ekvivalent jedinečnosti faktorizace.

Toto prohlášení je přeloženo takto:

Když rozpočítáme číslo do prvočinitelů, je velmi snadné najít všechny jeho dělitele. Musíme totiž nejprve vynásobit prvočinitele navzájem a pak je násobit po dvojicích, po třech, po čtyřech, po čtyřech, a tak dále, dokud nedojdeme k samotnému číslu.

„Zkušenost v teorii čísel“ ( francouzsky Essai sur la théorie des nombres , 1798) Legendre obsahuje důkaz o existenci rozkladu na prvočinitele a zvláštní předpoklad o jedinečnosti tohoto rozkladu výčtem všech prvočísel daného čísla. .

Legendreův výrok o existenci rozkladu zní [18] :

Jakékoli číslo , které není prvočíslo, může být reprezentováno jako součin několika prvočísel atd., z nichž každé je zvýšeno na určitou mocninu, takže lze vždy předpokládat atd. $N$ $\alpha ,\beta ,\gama$ ${\displaystyle N=\alpha ^{m}\beta ^{n}\gamma ^{p))$

Tvrzení související s jednoznačností faktorizace je uvedeno v odstavci 10 úvodu, kde měl Legendre v úmyslu zjistit počet všech dělitelů čísla a zároveň jejich součet. Jedinečnost lze z tohoto tvrzení snadno dokázat.

Carl Gauss (19. století)

První přesná formulace teorému a jeho důkaz jsou uvedeny v Gaussových aritmetických výzkumech (1801). Výrok věty lze nalézt v odstavci 16 a její překlad je následující:

Složené číslo lze jedinečným způsobem rozdělit na prvočinitele.

Aplikace

Největší společný dělitel a nejmenší společný násobek

Základní teorém aritmetiky poskytuje elegantní výrazy pro GCD a LCM .

Označte všemi různými prvočísly, na která byla čísla rozložena, a stupni , s nimiž se v těchto rozkladech vyskytují, resp . Je jasné, že mohou nabývat pouze přirozené nebo nulové hodnoty. ${p_{i}}$ $A$ $b$ ${d_{i))$ ${d'_{i))$ ${d_{i}}, {d'_{i}}$

Pak:

{\text{gcd}}(a,b)=p_{1}^{\min\{\,d_{1},d_{1}'\,\}}\cdot p_{2}^ {\min\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\min\{\,d_{3},d_{3}'\,\} }\cdot p_{4}^{\min\{\,d_{4},d_{4}'\,\))\cdot \ldots =\prod p_{i}^{\min\{\,d_ {i},d_{i}'\,\}};

{\text{LCD))(a,b)=p_{1}^{\max\{\,d_{1},d_{1}'\,\))\cdot p_{2}^ {\max\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\max\{\,d_{3},d_{3}'\,\} }\cdot p_{4}^{\max\{\,d_{4},d_{4}'\,\))\cdot \ldots =\prod p_{i}^{\max\{\,d_ {i},d_{i}'\,\}}.

Dělitelé přirozeného čísla

Když znáte rozklad přirozeného čísla, můžete okamžitě označit všechny jeho dělitele .

Použijeme kanonický rozklad čísla uvedeného na začátku článku. Přirozená čísla nejsou nic jiného než počet odpovídajících prvočísel , která se vyskytují při rozkladu původního čísla. Abychom našli všechny dělitele, stačí napsat součiny se všemi možnými kombinacemi prvočísel a měnit počet každého v součinu od do $n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k)),$ ${\displaystyle d_{1},\cdots ,d_{k))$ $p_{1},...,p_{k}$ $p_{i}$ $0$ $d_{i}$

Příklad: $N=1164=2\cdot 2\cdot 3\cdot 97=2^{2}\cdot 3^{1}\cdot 97^{1}.$

Protože se číslo 2 vyskytuje v expanzi 2x, může nabývat celočíselných hodnot od 0 do 2. Podobně nabývají hodnot od 0 do 1. Množina všech dělitelů se tedy skládá z čísel $d_{1}$ $d_{2}$ $d_{3}$

${\begin{alignedat}{2}1,\\2,\\3,\\97,\\2\cdot 2,\\2\cdot 3,\\2\cdot 97,\\3 \cdot 97,\\2\cdot 2\cdot 3,\\2\cdot 2\cdot 97,\\2\cdot 3\cdot 97,\\2\cdot 2\cdot 3\cdot 97.\end{ alignedat}}$ .

Chcete-li vypočítat celkový počet dělitelů, musíte vynásobit počet všech možných hodnot pro různé . $d_{k}$

V tomto příkladu je celkový počet dělitelů $2\cdot 2\cdot 3=12.$

Aritmetické funkce

Některé aritmetické funkce lze vypočítat pomocí kanonické prvočíselnosti.

Například pro Eulerovu funkci přirozeného čísla platí vzorec: kde je prvočíslo a prochází všemi hodnotami zapojenými do rozšíření na prvočinitele ( důkaz ). $\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,$ $p$ $n$

Faktorizace součinu přirozených čísel

Součin dvou čísel lze vypočítat takto:

a\cdot b=p_{1}^{d_{1}+d_{1}'}\,p_{2}^{d_{2}+d_{2}'}\,p_{3} ^{d_{3}+d_{3}'}\,p_{4}^{d_{4}+d_{4}'}\ldots =\prod p_{i}^{d_{i}+d_{ i}'},

kde je mocnina, se kterou se prvočíslo vyskytuje v rozšíření čísla . Příklad: ${d'_{i))$ ${p_{i}}$ $b$ $68\cdot 36=(2\cdot 2\cdot 17)\cdot (2\cdot 2\cdot 3\cdot 3)=2^{4}\cdot 3^{2}\cdot 17$

Základní věta aritmetiky v kruzích

Uvažujme základní teorém aritmetiky v obecnějším případě: v normových kroužcích a v euklidovských kroužcích .

Prstenec, který má algoritmus dělení se zbytkem, se nazývá euklidovský prsten. Pro jakýkoli euklidovský kruh lze důkaz základní věty aritmetiky provést přesně stejným způsobem jako pro přirozená čísla.

Základní věta aritmetiky v kruhu Gaussových celých čísel

Hlavní věta aritmetiky s mírnou korekcí (jmenovitě je objasněno, že faktory se berou nejen do pořadí posloupnosti, ale také do asociace - vlastnosti Gaussových čísel se získávají navzájem násobením dělitelem jednoty : 1, i , −1 nebo − i ) má místo v kruhu Gaussových celých čísel . Myšlenkou důkazu je najít algoritmus dělení se zbytkem v daném kruhu čísel [19] .

Nejedinečnost rozkladu v prstenci

Tato věta však neplatí pro všechny kruhy [19] .

Uvažujme například komplexní čísla ve tvaru , kde , jsou celá čísla. Součet a součin takových čísel budou čísla stejného druhu. Pak dostaneme prsten s normou . $a=m+in{\sqrt {5}}$ $m$ $n$ $N(a)=m^{2}+5n^{2}=|a|^{2}$

Pro číslo 6 v tomto prstenu existují dva různé rozklady: . Zbývá dokázat, že čísla jsou prvočísla. Dokažme, že číslo 2 je prvočíslo. Nechť číslo rozložíme na prvočinitele jako . Pak . A aby čísla a zůstala prvočísla, jedinou možností je, aby byly přesně 2. $6=2\cdot 3=(1-i{\sqrt {5)))(1+i{\sqrt {5)))$ $2,3,1\pm i{\sqrt {5}}$ $2$ $(m_{1}+in_{1}{\sqrt {5)))(m_{2}+in_{2}{\sqrt {5)))$ $4=|m_{1}+in_{1}{\sqrt {5}}|^{2}|m_{2}+in_{2}{\sqrt {5}}|^{2}= (m_{1}^{2}+5n_{1}^{2})(m_{2}^{2}+5n_{2}^{2})$ $m_{1}+in_{1}{\sqrt {5))$ $m_{2}+in_{2}{\sqrt {5}}$ $m_{1}^{2}+5n_{1}^{2}$ $m_{2}^{2}+5n_{2}^{2}$

Ale v uvažovaném kruhu nejsou žádná čísla s normou 2, takže takový rozklad je nemožný, takže číslo 2 je prvočíslo. S čísly se zachází podobně . $3.1\pm i{\sqrt {5}}$

Prsteny, ve kterých stále platí hlavní teorém aritmetiky, se nazývají faktoriál .

Viz také

Poznámky

↑ Davenport, 1965 .
↑ Žikov, 2000 , str. 112.
↑ Kalužnin, 1969 , s. 6-7.
↑ Weisstein, 2010 , pp. 1126.
↑ Davenport, 1965 , s. 15-16.
↑ Davenport, 1965 , s. 17-18.
↑ Davenport, 1965 , s. 26-27.
↑ 1 2 A. Göksel Ağargün a E. Mehmet Özkan, 2001 , s. 207.
↑ Davenport, 1965 , s. 17.
↑ Počátky Euklida. Knihy VII - X, 1949 , str. 33.
↑ Počátky Euklida. Knihy VII - X, 1949 , str. 34.
↑ Počátky Euklida. Knihy VII - X, 1949 , str. 83.
↑ Hendy, 1975 .
↑ Mullin, 1965 .
↑ A. Göksel Ağargün a E. Mehmet Özkan, 2001 , s. 209.
↑ A. Göksel Ağargün a E. Mehmet Özkan, 2001 , s. 211.
↑ A. Göksel Ağargün a E. Mehmet Özkan, 2001 , s. 212.
↑ AM Le Gendre, Essai sur la théorie des nombres , Paříž, VI (1798), s. 6.
↑ 1 2 Žikov, 2000 , str. 116.

Literatura

Vinogradov I.M. Základy teorie čísel . - Státní nakladatelství technické a teoretické literatury, 1952. - 180 s. — 10 000 výtisků.
Davenport G. Vyšší aritmetika / ed. Yu. V. Linnik , přel. B. Z. Moroz - M. : Nauka , 1965. - S. 15-38. — 176 str.
Žikov V.V. Základní teorém aritmetiky // Soros Educational Journal . - 2000. - T. 6 , č. 3 . - S. 112-117 .
Kalužnin L. A. Základní věta aritmetiky . — Populární přednášky o matematice . — M .: Nauka, 1969. — 32 s.
Courant R., Robbins G. Dodatek ke kapitole I, § 4.2 // Co je matematika? - MTSNMO , 2000. - 568 s.
Weisstein E. W. CRC Stručná encyklopedie matematiky (anglicky) - Druhé vydání - Chapman a Hall London , CRC Press , 2010. - 3242 s. — ISBN 978-1-4200-3522-3
A. Göksel Ağargün a E. Mehmet Özkan. Historický přehled základní věty aritmetiky // Historia Mathematica. - 2001. - Sv. 28. - S. 207-214. - doi : 10.1006/hmat.2001.2318 .
D.D. Mordukhai-Boltovskoy, I.N. Veselovský. Začátek Euklida. Knihy VII-X. - Státní nakladatelství technické a teoretické literatury, 1949. - 510 s.
MD Hendy. Euklides a základní teorém aritmetiky . - Historia Mathematica 05/1975, 1975.
A. A. Mullin. Matematicko-filosofické poznámky k novým větám podobným základní větě aritmetiky. — Notre Dame Journal of Formal Logic, 1965.

Slovníky a encyklopedie	Britannica (online)

Čísla podle charakteristik dělitelnosti
Obecná informace	Faktorizace celých čísel Dělitelnost unitární dělitel Funkce děliče prvočíslo Základní teorém aritmetiky Aritmetické číslo
Faktorizační formy	prvočíslo Složené číslo Semiprime obdélníkové číslo Sfénické číslo Číslo bez čtverců Plný násobek Perfektní stupeň Achillovo číslo hladké číslo Běžné číslo hrubé číslo neobvyklé číslo
S omezenými děliteli	dokonalé číslo Poněkud nedostatečná čísla Trochu nadbytečná čísla Multiperfektní číslo Hemiperfektní čísla hyperdokonalé číslo super dokonalé číslo unitární prvočíslo polodokonalé číslo pararytmické číslo Erdős-Nicolasovo číslo
Čísla s mnoha děliteli	Přebytečná čísla Primitivní nadbytečná čísla Vysoce nadbytečná čísla Super redundantní čísla Velmi nadbytečná čísla superkompozitní číslo Vysoce superkompozitní číslo podivné číslo
Souvisí s alikvotními sekvencemi	posvátné číslo přátelská čísla veřejná čísla Kvazi přátelská čísla
jiný	Nedostatek čísel čísla kamarádů sublimovaná čísla Rudná čísla skromné číslo Stejné číslice extravagantní číslo