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

С Википедије, слободне енциклопедије

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

1200 = 24 × 31 × 52 = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 = итд.

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

Сваки природан број је могуће написати као , где је — прост број, при чему је таква презентација тачна до редоследа чинилаца.
где су — прости бројеви, и — природни бројеви.

Важно је приметити да се број 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 и милијарду (109), има их 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 је прост број. Означимо га са p1. Тада мора бити n=p1n1, где је 1<n1<n. Математичка индукција ће даље дати да се и број n1 може затим факторисати. Према томе, може се факторисати и полазни број 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, онда се природан број може представити у облику

где је Такво представљање називамо канонски облик броја n.
Теорема 2
Сваки природан број има јединствен канонски облик.
Доказ
На основу теореме 1 канонско представљање постоји, а канонски облик простог броја је, очигледно, јединствен. За остале бројеве, доказ изводимо свођењем на контрадикцију. Претпоставимо да постоји природан број који се може представити у канонском облику на два различита начина. Нека је n најмањи такав број Ниједан од бројева p не може се појавити у обе канонске репрезентације броја n због претпоставке о минималности n. Бројеве је увек могуће поредати по величини и рецимо За просте факторе и важи па можемо узети да је Нека је Из следи где је Дакле број n-u може се написати у облику где су прости бројеви, за Међутим, из повлачи растављање на просте факторе, на пример па следи другачији запис броја где нема простог фактора То произилази из и са друге стране јер није делитељ од Дакле број n-u има две различите факторизације, јер само једна од њих садржи прост фактор То важи и у случају када је Међутим, а то је у контрадикцији са претпоставком о минималности броја n. Дакле, не постоји цео број већи од 1 који се може на два начина представити у канонском облику. Крај доказа.


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

Репрезентације[уреди | уреди извор]

Теорема 3
Нека су бројеви c и n дати у канонском облику
Тада је ако и само ако је за
Доказ
Следи из где је Крај доказа.

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ Long (1972, стр. 44)
  2. ^ Pettofrezzo & Byrkit (1970, стр. 53)
  3. ^ Hardy & Wright (2008, Thm 2)
  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. 

Литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]