Основна теорема аритметике

Основна теорема аритметике или „теорема о јединственој факторизацији” јесте тврђење да сваки природан број већи од 1 је или прост број или се може на јединствен начин представити као производ простих бројева, до нивоа редоследа чинилаца.^[1][2][3] На пример

1200 = 2⁴ × 3¹ × 5² = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 = итд.

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

Сваки природан број ${\displaystyle n>1}$ је могуће написати као ${\displaystyle n=p_{1}\cdot \dots \cdot p_{k}}$, где је ${\displaystyle p_{1},\dots ,p_{k}}$ — прост број, при чему је таква презентација тачна до редоследа чинилаца.

${\displaystyle \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}},}$ где су ${\displaystyle p_{1}<p_{2}<\dots <p_{k}}$ — прости бројеви, и ${\displaystyle d_{1},\dots ,d_{k}}$ — природни бројеви.

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

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

Прости бројеви, односно прим-бројеви су они који имају само два тачна делиоца: јединицу и самог себе.^[4][5][6][7] То је случај са 2, 3, 5, 7, 11, 13,17, 19, 23, .... По конвенцији сматра се да 1 није прост број.^[8][9] Простих бројева има бесконачно много, али што даље напредујемо у скупу природних бројева, то их све ређе налазимо: између 1 и 10 имамо 4 проста броја, што чини 40%; између 1 и 100 има 25 простих бројева, тј. 25%; између 1 и 1000 има их 144, дакле 14,4%; ...; између 1 и милијарду (10⁹), има их 48 254 942, тј. мање од 4,8%. Управо они, прости бројеви, су и највећа загонетка аритметике. У то се можемо уверити на сваком кораку.

Пример

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

Ипак, још пре пар хиљада година Еуклид је доказао основно правило аритметике: сваки природан број је или прост број или је производ простих бројева.^{[10][11][12][13]} У савременој формулацији основни став аритметике гласи: сваки природан број може се представити у облику производа простих фактора и његово представљање је јединствено до поретка фактора. То ће бити речено још прецизније у теореми 2, у низу од три наредне теореме.

Фактори

Теорема 1

Ако је n природан број, онда је n производ простих фактора.

Доказ

За прост број n тврђење важи очигледно, он је производ јединице и самог себе. Тврђење свакако важи за бројеве n = 1, 2, 3 и можда за још неке. Претпоставимо да тврђење важи за све сложене бројеве мање од n. Ако је и број n сложен број, тада постоји цео број c такав да је 1<c<n, c|n (ово последње читамо "c дели n", што значи да је број n дељив бројем c). Означимо са m најмањи од поменутих бројева c. Такав m не може бити сложен број, јер би тада постојао цео број k, такав да је 1<k<m, k|m, што би значило и k|n. Међутим, то је контрадикција са претпоставком да је m најмањи природан број који је делитељ од n. Дакле, број m је прост број. Означимо га са p₁. Тада мора бити n=p₁n₁, где је 1<n₁<n. Математичка индукција ће даље дати да се и број n₁ може затим факторисати. Према томе, може се факторисати и полазни број 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, онда се природан број може представити у облику

${\displaystyle n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}},}$ где је ${\displaystyle p_{1}<p_{2}<...<p_{k},\;\alpha _{i}>0,\;i=1,2,...,k.}$ Такво представљање називамо канонски облик броја n.

Теорема 2

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

Доказ

На основу теореме 1 канонско представљање постоји, а канонски облик простог броја је, очигледно, јединствен. За остале бројеве, доказ изводимо свођењем на контрадикцију. Претпоставимо да постоји природан број који се може представити у канонском облику на два различита начина. Нека је n најмањи такав број ${\displaystyle n=p_{1}p_{2}...p_{k}=q_{1}q_{2}...q_{m}.}$ Ниједан од бројева p не може се појавити у обе канонске репрезентације броја n због претпоставке о минималности n. Бројеве је увек могуће поредати по величини и рецимо ${\displaystyle p_{1}\leq p_{2}\leq ...\leq p_{k},\;q_{1}\leq q_{2}\leq ...\leq q_{m}.}$ За просте факторе ${\displaystyle p_{1}}$ и ${\displaystyle q_{1}}$ важи ${\displaystyle p_{1}\neq q_{1},}$ па можемо узети да је ${\displaystyle p_{1}<q_{1}.}$ Нека је ${\displaystyle u=p_{1}q_{2}...q_{m}.}$ Из ${\displaystyle p_{1}|u,p_{1}|n}$ следи ${\displaystyle p_{1}|(n-u),}$ где је ${\displaystyle n-u=(q_{1}-p_{1})q_{2}...q_{m}>1.}$ Дакле број n-u може се написати у облику ${\displaystyle n-u=p_{1}t_{1}...t_{h},}$ где су ${\displaystyle t_{i}}$ прости бројеви, за ${\displaystyle i=1,2,...,h.}$ Међутим, из ${\displaystyle q_{1}-p_{1}>1}$ повлачи растављање на просте факторе, на пример ${\displaystyle q_{1}-p_{1}=r_{1}r_{2}...r_{s},}$ па следи другачији запис броја ${\displaystyle n-u=r_{1}r_{2}...r_{s}q_{.}..q_{m},}$ где нема простог фактора ${\displaystyle p_{1}.}$ То произилази из ${\displaystyle p_{1}\neq q_{i},i=1,2,...,m,}$ и са друге стране ${\displaystyle p_{1}\neq r_{j},j=1,2,...,s,}$ јер ${\displaystyle p_{1}}$ није делитељ од ${\displaystyle q_{1}-p_{1}.}$ Дакле број n-u има две различите факторизације, јер само једна од њих садржи прост фактор ${\displaystyle p_{1}.}$ То важи и у случају када је ${\displaystyle q_{1}-p_{1}=1.}$ Међутим, ${\displaystyle 1<n-u<n,}$ а то је у контрадикцији са претпоставком о минималности броја n. Дакле, не постоји цео број већи од 1 који се може на два начина представити у канонском облику. Крај доказа.

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

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

Теорема 3

Нека су бројеви c и n дати у канонском облику

${\displaystyle c=\prod _{i=1}^{k}p_{i}^{\gamma _{i}},\quad n=\prod _{i=1}^{k}p_{i}^{\beta _{i}}.}$

Тада је ${\displaystyle c|n\,}$ ако и само ако је ${\displaystyle 0\leq \gamma _{i}\leq \beta _{i},}$ за ${\displaystyle i=1,2,...,k.\,}$

Доказ

Следи из ${\displaystyle n=cm,\;m=\prod _{i=1}^{k}p_{i}^{\alpha _{i}},}$ где је ${\displaystyle \alpha _{i}=\beta _{i}-\gamma _{i},i=1,2,...,k.\,}$ Крај доказа.

Види још

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

Референце

1. Long (1972, стр. 44)
2. Pettofrezzo & Byrkit (1970, стр. 53)
3. Hardy & Wright (2008, Thm 2) harv грешка: no target: CITEREFHardyWright2008 (help)
4. Gardiner, Anthony (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996. Oxford University Press. стр. 26. ISBN 978-0-19-850105-3.
5. Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2nd изд.). Routledge. стр. 62. ISBN 978-1-136-63662-2.
6. Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. стр. 16. OCLC 6975809.
7. Leff, Lawrence S. (2000). Math Workbook for the SAT I. Barron's Educational Series. стр. 360. ISBN 978-0-7641-0768-9.
8. Dudley, Underwood (1978). „Section 2: Unique factorization”. Elementary number theory (2nd изд.). W.H. Freeman and Co. стр. 10. ISBN 978-0-7167-0076-0.
9. Sierpiński, Wacław (1988). Elementary Theory of Numbers. North-Holland Mathematical Library. 31 (2nd изд.). Elsevier. стр. 113. ISBN 978-0-08-096019-7.
10. Joshi, Kirti (1994). „Notes on Diophantus”. Current Science. 67 (12): 957—966. ISSN 0011-3891.
11. A. Goksel Agargun and E. Mehmet Özkan. „A Historical Survey of the Fundamental Theorem of Arithmetic” (PDF). Historia Mathematica: 209. „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.”
12. Rashed, Roshdi (2002-09-11). Encyclopedia of the History of Arabic Science (на језику: енглески). Routledge. стр. 385. ISBN 9781134977246. „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.”
13. Christianidis, Jean; Oaks, Jeffrey (2022-11-02). The Arithmetica of Diophantus: A Complete Translation and Commentary (на језику: енглески) (1 изд.). London: Routledge. ISBN 978-1-315-17147-0. doi:10.4324/9781315171470.

Литература

• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae (Second, corrected edition), Превод: Clarke, Arthur A., New York: Springer, ISBN 978-0-387-96254-2
• Gauss, Carl Friedrich (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition) (на језику: немачки), Превод: Maser, H., New York: Chelsea, ISBN 0-8284-0191-8
• Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Comment. Soc. regiae sci, Göttingen 6
• Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, Göttingen: Comment. Soc. regiae sci, Göttingen 7
• Euclid (1956), The thirteen books of the Elements, 2 (Books III-IX), Translated by Thomas Little Heath (Second Edition Unabridged изд.), New York: Dover, ISBN 978-0-486-60089-5
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd изд.), Lexington: D. C. Heath and Company, LCCN 77-171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766
• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5
• Weil, André (2007) [1984], Number Theory: An Approach through History from Hammurapi to Legendre, Modern Birkhäuser Classics, Boston, MA: Birkhäuser, ISBN 978-0-817-64565-6
• Goles, E.; Schulz, O.; Markus, M. (2001). „Prime number selection of cycles in a predator-prey model”. Complexity. 6 (4): 33—38. Bibcode:2001Cmplx...6d..33G. doi:10.1002/cplx.1040.
• Campos, Paulo R.A.; de Oliveira, Viviane M.; Giro, Ronaldo; Galvão, Douglas S. (2004). „Emergence of prime numbers as the result of evolutionary strategy”. Physical Review Letters. 93 (9): 098107. Bibcode:2004PhRvL..93i8107C. PMID 15447148. S2CID 88332. arXiv:q-bio/0406017 . doi:10.1103/PhysRevLett.93.098107.
• „Invasion of the Brood”. The Economist. 6. 5. 2004. Приступљено 2006-11-26.CS1 одржавање: Формат датума (веза)
• Zimmer, Carl (15. 5. 2015). „Bamboo Mathematicians”. Phenomena: The Loom. National Geographic. Архивирано из оригинала 17. 05. 2015. г. Приступљено 22. 2. 2018.CS1 одржавање: Формат датума (веза)

Спољашње везе

• Why isn’t the fundamental theorem of arithmetic obvious?
• GCD and the Fundamental Theorem of Arithmetic at cut-the-knot.
• PlanetMath: Proof of fundamental theorem of arithmetic
• 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.
• "Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.
• Grime, James, „1 and Prime Numbers”, Numberphile, Brady Haran, Архивирано из оригинала 2021-12-11. г.