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

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

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

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

Секој природен број

n>1

може да се напише како

n=p_{1}\cdot \dots \cdot p_{k}

, каде што

p_{1},\dots ,p_{k}

— е прост број, при што таквата презентација е точна до редоследот на множителите.

\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}},

каде

p_{1}<p_{2}<\dots <p_{k}

- се прости броеви, и

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=2x78=2x2x39=2x2x3x13. Значи 2, 2, 3, 13 се прости броеви, фактори на бројот 156.

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

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

Со групирање на еднакви прости множители на бројот n, тогаш природниот број може да се претстави во облик

n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}},

при што

p_{1}<p_{2}<...<p_{k},\;\alpha _{i}>0,\;i=1,2,...,k.

Таквото претставување го нарекуваме канонски облик на бројот n.

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

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

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

Претставувања

Теорема 3

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

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

Тогаш

c|n\,

ако и само ако

0\leq \gamma _{i}\leq \beta _{i},

за

i=1,2,...,k.\,

Доказ

Следи од

n=cm,\;m=\prod _{i=1}^{k}p_{i}^{\alpha _{i}},

при што

\alpha _{i}=\beta _{i}-\gamma _{i},i=1,2,...,k.\,

Крај на доказот.

Поврзано

Наводи

↑ Long (1972, стр. 44)
↑ Pettofrezzo & Byrkit (1970, стр. 53)
↑ Hardy & Wright (2008)
↑ 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.
↑ Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2nd. изд.). Routledge. стр. 62. ISBN 978-1-136-63662-2.
↑ Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. стр. 16. OCLC 6975809.
↑ Leff, Lawrence S. (2000). Math Workbook for the SAT I. Barron's Educational Series. стр. 360. ISBN 978-0-7641-0768-9.
↑ Dudley, Underwood (1978). „Section 2: Unique factorization“. Elementary number theory (2nd. изд.). W.H. Freeman and Co. стр. 10. ISBN 978-0-7167-0076-0.
↑ Sierpiński, Wacław (1988). Elementary Theory of Numbers. North-Holland Mathematical Library. 31 (2nd. изд.). Elsevier. стр. 113. ISBN 978-0-08-096019-7.
↑ Joshi, Kirti (1994). „Notes on Diophantus“. Current Science. 67 (12): 957–966. ISSN 0011-3891.
↑ 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.
↑ 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.
↑ Christianidis, Jean; Oaks, Jeffrey (2022-11-02). The Arithmetica of Diophantus: A Complete Translation and Commentary (англиски) (1. изд.). London: Routledge. doi:10.4324/9781315171470. ISBN 978-1-315-17147-0.

Литература

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. arXiv:q-bio/0406017. Bibcode:2004PhRvL..93i8107C. doi:10.1103/PhysRevLett.93.098107. PMID 15447148. S2CID 88332.
„Invasion of the Brood“. The Economist. May 6, 2004. Посетено на 2006-11-26.
Zimmer, Carl (May 15, 2015). „Bamboo Mathematicians“. Phenomena: The Loom. National Geographic. Архивирано од изворникот на 2015-05-17. Посетено на February 22, 2018.

Надворешни врски

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, Архивирано од изворникот на 2023-08-07, Посетено на 2023-10-09CS1-одржување: бот: непознат статус на изворната URL (link)

[1] Long (1972, стр. 44)

[2] Pettofrezzo & Byrkit (1970, стр. 53)

[3] Hardy & Wright (2008)

[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. doi:10.4324/9781315171470. ISBN 978-1-315-17147-0.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]