Преглед на кодот на Основна теорема на аритметиката

'''Основната теорема на аритметиката''' или „теоремата за единствена факторизација“ е тврдењето дека секој [[природен број]] поголем од 1 е или [[прост број]] или може единствено да се претстави како производ на прости броеви, до нивото на редослед на множители.<ref>{{Harvard citation text|Long|1972|p=44}}</ref><ref>{{Harvard citation text|Pettofrezzo|Byrkit|1970|p=53}}</ref><ref>{{Harvard citation text|Hardy|Wright|2008}}</ref> На пр

1200 = 2{{sup|4}} &#xD7; 3{{sup|1}} &#xD7; 5{{sup|2}} = 3 &#xD7; 2 &#xD7; 2 &#xD7; 2 &#xD7; 2 &#xD7; 5 &#xD7; 5 = 5 &#xD7; 2 &#xD7; 3 &#xD7; 2 &#xD7; 5 &#xD7; 2 &#xD7; 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>{{Наведена книга|url=https://archive.org/details/mathematicalolym1997gard|title=The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996|last=Gardiner|first=Anthony|publisher=Oxford University Press|year=1997|isbn=978-0-19-850105-3|page=[https://archive.org/details/mathematicalolym1997gard/page/26 26]|author-link=Tony Gardiner|url-access=registration}}</ref><ref>{{Наведена книга|url=https://books.google.com/books?id=uy-yGVRUilMC&pg=PA62|title=Dyslexia, Dyscalculia and Mathematics: A practical guide|last=Henderson|first=Anne|publisher=Routledge|year=2014|isbn=978-1-136-63662-2|edition=2nd|page=62}}</ref><ref>{{Наведена книга|url=https://archive.org/details/giantgoldenbooko00adle|title=The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space|last=Adler|first=Irving|publisher=Golden Press|year=1960|page=[https://archive.org/details/giantgoldenbooko00adle/page/16 16]|oclc=6975809|author-link=Irving Adler|url-access=registration}}</ref><ref>{{Наведена книга|url=https://archive.org/details/barronsmathworkb00leff_0|title=Math Workbook for the SAT I|last=Leff|first=Lawrence S.|publisher=Barron's Educational Series|year=2000|isbn=978-0-7641-0768-9|page=[https://archive.org/details/barronsmathworkb00leff_0/page/360 360]|url-access=registration}}</ref> Ваков случај е со 2, 3, 5, 7, 11, 13, 17, 19, 23, .... По [[конвенција]], 1 се смета дека не е прост број.<ref>{{Наведена книга|url=https://archive.org/details/elementarynumber00dudl_0/page/10|title=Elementary number theory|last=Dudley|first=Underwood|publisher=W.H. Freeman and Co.|year=1978|isbn=978-0-7167-0076-0|edition=2nd|page=[https://archive.org/details/elementarynumber00dudl_0/page/10 10]|chapter=Section 2: Unique factorization|author-link=Underwood Dudley|chapter-url=https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA10}}</ref><ref>{{Наведена книга|url=https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA113|title=Elementary Theory of Numbers|last=Sierpiński|first=Wacław|publisher=Elsevier|year=1988|isbn=978-0-08-096019-7|edition=2nd|series=North-Holland Mathematical Library|volume=31|page=113|author-link=Wacław Sierpiński}}</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>{{Наведено списание|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>{{Наведено списание|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>{{Наведена книга|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|last=Rashed|first=Roshdi|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>{{Наведена книга|url=https://www.taylorfrancis.com/books/9781315171470|title=The Arithmetica of Diophantus: A Complete Translation and Commentary|last=Christianidis|first=Jean|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 &#x3C; ''c'' &#x3C; ''n'', ''c|n'' (последното го читаме „ ''c'' го дели ''n'' “, што значи дека бројот ''n'' е делив со бројот ''c''). Со ''m'' да го означиме најмалиот од наведените броеви ''c''. Таков ''m'' не може да биде комплексен број, бидејќи тогаш би имало цел број ''k'' таков што 1 &#x3C; ''k'' &#x3C; ''m'', ''k|m'', што исто така би значело ''k|n''. Сепак, ова е во спротивност со претпоставката дека ''m'' е најмалиот природен број што е делив со ''n''. Според тоа, бројот ''m'' е прост број. Да го означиме со ''p''<sub>1</sub>. Тогаш мора да биде ''n=p''<sub>1</sub>''n''<sub>1</sub>, каде што 1 &#x3C; ''n''<sub>1</sub> &#x3C; ''n''. [[Математичка индукција|Математичката индукција]] дополнително ќе покаже дека бројот ''n''<sub>1</sub> потоа може да се факторизира. Според тоа, почетниот број ''n'' исто така може да се факторизира. Крај на доказот.

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

; Пример 2
: За да се подели одреден број на прости множители, постепено ќе проверуваме дали е делив со два, со три, со пет, и редум со прости броеви. За тоа можеме да користиме критериуми за деливост. Да речеме, 156=2x78=2x2x39=2x2x3x13. Значи 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> Значи, бројот ''nu'' може да се напише во облик <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, тоа се броеви од облик 4x+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> Крај на [[Докази|доказот]].

== Поврзано ==
* [[Ератостеново сито]]
* [[Риманова зета-функција]]

== Наводи ==
{{наводи}} 

== Литература ==
{{refbegin |30em}}
* {{citation
  | last = Gauss
  | first = Carl Friedrich
  | translator-last = Clarke
  | translator-first = Arthur A.
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
  | publisher = 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|archive-date=2006-05-15|archive-url=https://web.archive.org/web/20060515184334/http://economist.com/PrinterFriendly.cfm?Story_ID=2647052|url-status=dead}}
* {{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=2015-05-17|archive-url=https://web.archive.org/web/20150517210059/http://phenomena.nationalgeographic.com/2015/05/15/bamboo-mathematicians/|url-status=dead}}
{{refend}}

== Надворешни врски ==
* [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.
* {{Наведување|last=Grime|first=James|title=1 and Prime Numbers|url=https://www.youtube.com/watch?v=IQofiPqhJ_s|archiveurl=https://web.archive.org/web/20230807162635/https://www.youtube.com/watch?v=IQofiPqhJ_s|archivedate=2023-08-07|work=Numberphile|publisher=Brady Haran|accessdate=2023-10-09|url-status=bot: unknown}}

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

[[Категорија:CS1-одржување: датумски формат]]
[[Категорија:Статии со извори на германски (de)]]
[[Категорија:Фундаментални теореми]]
[[Категорија:Факторизација]]