Изворни код странице Основна теорема аритметике

'''Основна теорема аритметике''' или „теорема о јединственој факторизацији” јесте тврђење да сваки [[природан број]] већи од 1 је или [[прост број]] или се може на јединствен начин представити као производ простих бројева, до нивоа редоследа чинилаца.<ref>{{harvtxt|Long|1972|p=44}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=53}}</ref><ref>{{Harvtxt|Hardy|Wright|2008|loc=Thm 2}}</ref> На пример

1200 = 2{{sup|4}} &times; 3{{sup|1}} &times; 5{{sup|2}} = 3 &times; 2 &times; 2 &times; 2 &times; 2 &times; 5 &times; 5 = 5 &times; 2 &times; 3 &times; 2 &times; 5 &times; 2 &times; 2 = итд.

односно, прво је значајно да се број 1200 може представити као производ простих бројева, и друго то су увек искључиво четири двојке, једна тројка и две петице (евентуално у другачијем распореду).

:Сваки природан број <math>n>1</math> је могуће написати као <math>n=p_1\cdot\dots\cdot p_k</math>, где је <math>p_1,\dots,p_k</math> — прост број, при чему је таква презентација тачна до редоследа чинилаца.

: <math>\forall n \in \mathbb{N}, n = p_1^{d_1} \cdot p_2^{d_2} \cdot \dots \cdot p_k^{d_k} = \prod_{i=1}^{k}p_i^{d_i} ,</math> где су <math>p_1 < p_2 < \dots < p_k</math> — прости бројеви, и <math>d_1,\dots,d_k</math> — природни бројеви.

Важно је приметити да се број 1 не третира као прост број, јер факторизација више не би била једнозначна, као код 2 = 2×1 = 2×1×1 = ...

== Основна теорема ==

[[Прост број|Прости бројеви]], односно ''прим-бројеви'' су они који имају само два тачна делиоца: јединицу и самог себе.<ref>{{cite book|title=The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996|first=Anthony|last=Gardiner|author-link=Tony Gardiner|publisher=Oxford University Press|year=1997|isbn=978-0-19-850105-3|page=[https://archive.org/details/mathematicalolym1997gard/page/26 26]|url=https://archive.org/details/mathematicalolym1997gard|url-access=registration}}</ref><ref>{{cite book|title=Dyslexia, Dyscalculia and Mathematics: A practical guide|first=Anne|last=Henderson|edition=2nd |publisher=Routledge|year=2014|isbn=978-1-136-63662-2|page=62|url=https://books.google.com/books?id=uy-yGVRUilMC&pg=PA62}}</ref><ref>{{cite book|title=The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space|url=https://archive.org/details/giantgoldenbooko00adle|url-access=registration |first=Irving|last=Adler|author-link=Irving Adler|publisher=Golden Press|year=1960|page=[https://archive.org/details/giantgoldenbooko00adle/page/16 16]|oclc=6975809}}</ref><ref>{{cite book | url = https://archive.org/details/barronsmathworkb00leff_0 | url-access = registration | page = [https://archive.org/details/barronsmathworkb00leff_0/page/360 360] | title = Math Workbook for the SAT I | first = Lawrence S. | last = Leff | publisher = Barron's Educational Series | year = 2000 | isbn = 978-0-7641-0768-9}}</ref> То је случај са 2, 3, 5, 7, 11, 13,17, 19, 23, .... По [[конвенција|конвенцији]] сматра се да 1 није прост број.<ref>{{cite book | last1=Dudley | first1=Underwood | author-link=Underwood Dudley | title=Elementary number theory | publisher=W.H. Freeman and Co. | edition=2nd | isbn=978-0-7167-0076-0 | year=1978 | contribution=Section 2: Unique factorization | page=[https://archive.org/details/elementarynumber00dudl_0/page/10 10] | contribution-url=https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA10 | url=https://archive.org/details/elementarynumber00dudl_0/page/10 }}</ref><ref>{{cite book | last = Sierpiński | first = Wacław | author-link = Wacław Sierpiński | title = Elementary Theory of Numbers | edition = 2nd | volume = 31 | series = North-Holland Mathematical Library | publisher = Elsevier | year = 1988 | isbn = 978-0-08-096019-7 | page = 113 | url = https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA113 }}</ref> Простих бројева има [[бесконачност|бесконачно]] много, али што даље напредујемо у скупу природних бројева, то их све ређе налазимо: између 1 и 10 имамо 4 проста броја, што чини 40%; између 1 и 100 има 25 простих бројева, тј. 25%; између 1 и 1000 има их 144, дакле 14,4%; ...; између 1 и милијарду (10<sup>9</sup>), има их 48 254 942, тј. мање од 4,8%. Управо они, прости бројеви, су и највећа загонетка аритметике. У то се можемо уверити на сваком кораку. 

; Пример: Прости бројеви су ''близанци'' ако им је разлика два (близанци су 3 и 5, или 4001 и 4003). Питање без одговора у данашњој математици је: има ли близанаца бесконачно или не?

Ипак, још пре пар хиљада година [[Еуклид]] је доказао ''основно правило аритметике'': сваки [[природан број]] је или прост број или је производ простих бројева.<ref>{{Cite journal |last=Joshi |first=Kirti |date=1994 |title=Notes on Diophantus |url=https://www.jstor.org/stable/24096781 |journal=Current Science |volume=67 |issue=12 |pages=957–966 |issn=0011-3891}}</ref><ref>{{Cite journal |last=A. Goksel Agargun and E. Mehmet Özkan |title=A Historical Survey of the Fundamental Theorem of Arithmetic |url=https://core.ac.uk/download/pdf/82721726.pdf |journal=Historia Mathematica |pages=209 |quote=One could say that Euclid takes the first step on the way to the existence of prime factorization, and Diophantus takes the final step by actually proving the existence of a finite prime factorization in his first proposition.}}</ref><ref>{{Cite book |last=Rashed |first=Roshdi |url=https://books.google.com/books?id=7veIAgAAQBAJ&q=fundamental+theorem+of+arithmetic+discovered+al-farisi&pg=PA385 |title=Encyclopedia of the History of Arabic Science |date=2002-09-11 |publisher=Routledge |isbn=9781134977246 |page=385 |language=en |quote=The famous mathematician Diophantus compiled a paper in which he set out deliberately to prove the theorem of Euclid in an algebraic way. This forced him to an understanding of the first arithmetical functions and to a full preparation which led him to state for the first time the fundamental theorem of arithmetic.}}</ref><ref>{{Cite book |last=Christianidis |first=Jean |url=https://www.taylorfrancis.com/books/9781315171470 |title=The Arithmetica of Diophantus: A Complete Translation and Commentary |last2=Oaks |first2=Jeffrey |date=2022-11-02 |publisher=Routledge |isbn=978-1-315-17147-0 |edition=1 |location=London |language=en |doi=10.4324/9781315171470}}</ref> У савременој формулацији '''основни став [[аритметика|аритметике]] гласи''': сваки [[природан број]] може се представити у облику [[производ]]а простих фактора и његово представљање је јединствено до поретка фактора. То ће бити речено још прецизније у теореми 2, у низу од три наредне теореме.

=== Фактори ===

; Теорема 1: Ако је ''n'' природан број, онда је ''n'' производ простих фактора.
; Доказ: За [[прост број]] ''n'' [[тврђење]] важи очигледно, он је производ јединице и самог себе. Тврђење свакако важи за бројеве ''n'' = 1, 2, 3 и можда за још неке. Претпоставимо да тврђење важи за све сложене бројеве мање од ''n''. Ако је и број ''n'' [[сложен број]], тада постоји [[цео број]] ''c'' такав да је 1&lt;''c''&lt;''n'', ''c|n'' (ово последње читамо "''c'' дели ''n''", што значи да је број ''n'' дељив бројем ''c''). Означимо са ''m'' најмањи од поменутих бројева ''c''. Такав ''m'' не може бити сложен број, јер би тада постојао цео број ''k'', такав да је 1&lt;''k''&lt;''m'', ''k|m'', што би значило и ''k|n''. Међутим, то је контрадикција са претпоставком да је ''m'' најмањи природан број који је делитељ од ''n''. Дакле, број ''m'' је прост број. Означимо га са ''p''<sub>1</sub>. Тада мора бити ''n=p''<sub>1</sub>''n''<sub>1</sub>, где је 1&lt;''n''<sub>1</sub>&lt;''n''. [[Математичка индукција]] ће даље дати да се и број ''n''<sub>1</sub> може затим факторисати. Према томе, може се факторисати и полазни број ''n''. Крај доказа.

; Пример 1: У самопослузи се јаја продају у паковањима од по дванаест јаја. Свако од тих паковања можемо распаковати у по три мања пакета са по четири јајета, зато што је број 12 дељив са 3 и са 4, тако да је 3х4=12.

; Пример 2: Да бисмо раставили неки број на просте чиниоце поступно ћемо проверавати да ли је дељив са два, са три, са пет, и редом са простим бројевима. За то можемо користити критеријуме дељивости. Рецимо, 156=2х78=2х2х39=2х2х3х13. Дакле, 2, 2, 3, 13 су прости бројеви, фактори броја 156.

; Критеријуми дељивости: број је дељив са 2 ако се завршава са нулом или парном цифром; 
: дељив је са 3, ако је збир цифара дељив са 3; 
: са 5 ако се завршава нулом или петицом; 
: број је дељив са 11 ако је збир цифара тог броја на непарним позицијама одузет од збира његових цифара на парним позицијама једнак нули или је дељив са 11.

=== Канонски облик ===

Групишући једнаке просте факторе броја n, онда се природан број може представити у облику
: <math>n=\prod_{i=1}^kp_i^{\alpha_i},</math> где је <math>p_1<p_2<...<p_k,\; \alpha_i>0,\; i=1,2,...,k.</math> Такво представљање називамо [[канонски облик]] броја n.

; Теорема 2: Сваки природан број има јединствен канонски облик.

; Доказ: На основу теореме 1 канонско представљање постоји, а канонски облик [[прост број|простог броја]] је, очигледно, јединствен. За остале [[број]]еве, [[доказ]] изводимо [[свођење на контрадикцију|свођењем на контрадикцију]]. Претпоставимо да постоји [[природан број]] који се може представити у канонском облику на два различита начина. Нека је ''n'' најмањи такав број <math>n=p_1p_2...p_k=q_1q_2...q_m.</math> Ниједан од бројева ''p'' не може се појавити у обе канонске репрезентације броја ''n'' због претпоставке о минималности ''n''. Бројеве је увек могуће поредати по величини и рецимо <math>p_1\le p_2\le ...\le p_k, \; q_1\le q_2 \le ... \le q_m.</math> За просте факторе <math>p_1</math> и <math>q_1</math> важи <math>p_1 \ne q_1,</math> па можемо узети да је <math>p_1 < q_1.</math> Нека је <math>u=p_1q_2...q_m.</math> Из <math>p_1|u,p_1|n</math> следи <math>p_1|(n-u),</math> где је <math>n-u=(q_1-p_1)q_2...q_m>1.</math> Дакле број ''n-u'' може се написати у облику <math>n-u=p_1t_1...t_h,</math> где су <math>t_i</math> прости бројеви, за <math>i=1,2,...,h.</math> Међутим, из <math>q_1-p_1>1</math> повлачи растављање на просте факторе, на пример <math>q_1-p_1=r_1r_2...r_s,</math> па следи другачији запис броја <math>n-u=r_1r_2...r_sq_...q_m,</math> где нема простог фактора <math>p_1.</math> То произилази из <math>p_1\ne q_i,i=1,2,...,m,</math> и са друге стране <math>p_1\ne r_j, j=1,2,...,s,</math> јер <math>p_1</math> није делитељ од <math>q_1-p_1.</math> Дакле број ''n-u'' има две различите факторизације, јер само једна од њих садржи прост фактор <math>p_1.</math> То важи и у случају када је <math>q_1-p_1=1.</math> Међутим, <math>1<n-u<n,</math> а то је у контрадикцији са претпоставком о минималности броја ''n''. Дакле, не постоји цео број већи од 1 који се може на два начина представити у канонском облику. Крај [[доказ]]а.


То је ''основна [[теорема]] аритметике''. Постоји много различитих [[доказ]]а ове теореме и ниједан није тривијалан, јер се на крају ослања на посебности [[скуп]]а природних бројева у односу, рецимо на његове затворене подскупове. На пример, скуп парних бројева је подскуп скупа свих природних бројева '''N''' и такође је затворен на операције сабирања и множења, као и '''N'''. Парни бројеви који при дељењу са 4 дају остатак 2, то су бројеви облика 4k+2, називају се ''парно-прости''. Сваки паран број може се представити у облику производа парно-простих бројева. Међутим, разлагање на парно-просте факторе није увек јединствено. Број 360 може се факторисати на парно-просте бројеве на више начина: 2x2x90=2x6x30=2x10=6x6x10.

=== Репрезентације ===

; [[Теорема]] 3: Нека су [[број]]еви c и n дати у [[канонски облик|канонском облику]]
:: <math>c=\prod_{i=1}^kp_i^{\gamma_i}, \quad n=\prod_{i=1}^kp_i^{\beta_i}.</math>
: Тада је <math>c|n\,</math> ако и само ако је <math>0\le \gamma_i \le \beta_i,</math> за <math>i = 1, 2, ..., k.\,</math>
; Доказ: Следи из <math>n=cm, \; m=\prod_{i=1}^kp_i^{\alpha_i},</math> где је <math>\alpha_i=\beta_i-\gamma_i, i=1,2,...,k.\,</math> Крај [[доказ]]а.

==Види још==
* Ратко Тошић, мр Вања Вукосавлавчевић, ''Елементи теорије бројева'', Алеф, Нови Сад, 1995.
* [[Ератостеново сито]]
* [[Риманова зета-функција]]

== Референце ==
{{reflist|}}

== Литература ==
{{Литература |30em}}
* {{citation
  | last = Gauss  | first = Carl Friedrich
  | translator-last = Clarke | translator-first = Arthur A.
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | year = 1986
  | isbn = 978-0-387-96254-2
  | url = https://www.springer.com/mathematics/algebra/book/978-0-387-96254-2
}}
* {{citation
  | last = Gauss  | first = Carl Friedrich
  | translator-last = Maser | translator-first = H.
  | language = de
  | title = Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
  | publisher = Chelsea
  | location = New York
  | year = 1965
  | isbn = 0-8284-0191-8}}
* {{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | title = Theoria residuorum biquadraticorum, Commentatio prima
  | publisher = Comment. Soc. regiae sci, Göttingen 6
  | location = Göttingen
  | year = 1828}}
* {{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | title = Theoria residuorum biquadraticorum, Commentatio secunda
  | publisher = Comment. Soc. regiae sci, Göttingen 7
  | location = Göttingen
  | year = 1832}}
* {{citation
  | author1 = Euclid
  | author1-link = Euclid
  | others = Translated by [[Thomas Little Heath]]
  | title = The thirteen books of the Elements
  | edition = Second Edition Unabridged
  | volume = 2 (Books III-IX)
  | publisher = [[Dover]]
  | location = New York
  | year = 1956
  | isbn = 978-0-486-60089-5
  | url = https://archive.org/details/thirteenbooksofe00eucl
  | url-access = registration
  | ref = {{harvid|Euclid|Heath|1956}}
  }}
* {{citation
 | first1 = Calvin T.
 | last1 = Long
 | year = 1972
 | title = Elementary Introduction to Number Theory
 | edition = 2nd | publisher = [[D. C. Heath and Company]]
 | location = Lexington
 | lccn = 77-171950
}}.
* {{citation
 | first1 = Anthony J.
 | last1 = Pettofrezzo
 | first2 = Donald R.
 | last2 = Byrkit
 | year = 1970
 | title = Elements of Number Theory
 | publisher = [[Prentice Hall]]
 | location = Englewood Cliffs
 | lccn = 77-81766
}}
* {{citation | last1 = Riesel  | first1 = Hans | title = Prime Numbers and Computer Methods for Factorization (second edition) | publisher = Birkhäuser | location = Boston | year = 1994 | isbn = 0-8176-3743-5}}
* {{citation |last= Weil |first= André |year= 2007 |orig-year= 1984 |title= [[Number Theory: An Approach through History from Hammurapi to Legendre]] |series= Modern Birkhäuser Classics |location= Boston, MA |publisher= Birkhäuser |isbn= 978-0-817-64565-6 }}
* {{cite journal |last1=Goles |first1=E. |last2=Schulz |first2=O. |first3=M. |last3=Markus |year=2001 |title=Prime number selection of cycles in a predator-prey model |journal=[[Complexity (journal)|Complexity]] |volume=6 |issue=4 |pages=33–38 |doi=10.1002/cplx.1040 |bibcode=2001Cmplx...6d..33G }}
* {{cite journal |first1=Paulo R.A.|last1=Campos |first2=Viviane M.|last2=de Oliveira |first3=Ronaldo|last3=Giro |first4=Douglas S.|last4=Galvão | journal = [[Physical Review Letters]] | title = Emergence of prime numbers as the result of evolutionary strategy | volume = 93 | doi = 10.1103/PhysRevLett.93.098107 |pmid=15447148 | issue = 9 | year = 2004 | page = 098107 | bibcode=2004PhRvL..93i8107C|arxiv = q-bio/0406017 |s2cid=88332 }}
* {{cite news |newspaper=[[The Economist]]| url=http://economist.com/PrinterFriendly.cfm?Story_ID=2647052 |title=Invasion of the Brood |date=May 6, 2004|access-date=2006-11-26 }}
* {{cite magazine|last1=Zimmer|first1=Carl|author-link=Carl Zimmer|date=May 15, 2015|title=Bamboo Mathematicians|url=http://phenomena.nationalgeographic.com/2015/05/15/bamboo-mathematicians/|department=Phenomena: The Loom|magazine=[[National Geographic]]|access-date=February 22, 2018|archive-date=17. 05. 2015|archive-url=https://web.archive.org/web/20150517210059/http://phenomena.nationalgeographic.com/2015/05/15/bamboo-mathematicians/|url-status=}}
{{Литература крај}}

== Спољашње везе ==
{{Commons category|Fundamental theorem of arithmetic}}
* [https://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious Why isn’t the fundamental theorem of arithmetic obvious?]
* [http://www.cut-the-knot.org/blue/gcd_fta.shtml GCD and the Fundamental Theorem of Arithmetic] at [[cut-the-knot]].
* [http://planetmath.org/fundamentaltheoremofarithmeticproofofthe PlanetMath: Proof of fundamental theorem of arithmetic]
* [http://fermatslasttheorem.blogspot.com/2005/06/unique-factorization.html Fermat's Last Theorem Blog: Unique Factorization], a blog that covers the history of [[Fermat's Last Theorem]] from [[Diophantus of Alexandria]] to the proof by [[Andrew Wiles]].
* [http://demonstrations.wolfram.com/FundamentalTheoremOfArithmetic/ "Fundamental Theorem of Arithmetic"] by Hector Zenil, [[Wolfram Demonstrations Project]], 2007.
* {{citation|last=Grime|first=James|title=1 and Prime Numbers|url=https://www.youtube.com/watch?v=IQofiPqhJ_s| archive-url=https://ghostarchive.org/varchive/youtube/20211211/IQofiPqhJ_s| archive-date=2021-12-11 | url-status=live|work=Numberphile|publisher=[[Brady Haran]]}}{{cbignore}}

{{нормативна контрола}}

[[Категорија:Фундаменталне теореме]]
[[Категорија:Број]]