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

Из пројекта Википедија

Основна теорема аритметике јесте тврђење да се сваки природан број може на јединствен начин представити као производ својих простих чинилаца.

Аритметика (грчки: αριθοζ - број) је наука о броју и операцијама са бројевима. У аритметици се првенствено изучава природан број и разломак и то је једна од најстаријих области људског знања.

Као наставни предмет, аритметика се у основној школи предаје на описним дефиницијама; на многим природно - математичким факултетима у свету изучава се веома темељито, обично у оквиру предмета: Основе аритметике, Теорија бројева, Аритметика рационалних бројева.

У модерној математици, речју аритметика често се као синонимом означава теорија бројева.

Садржај

[уреди] Основна теорема

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

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

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

[уреди] Фактори

Теорема 1
Ако је n природан број, онда је n производ простих фактора.
Доказ
За прост број n тврђење важи очигледно, он је производ јединице и самог себе. Тврђење свакако важи за бројеве n = 1, 2, 3 и можда за још неке. Претпоставимо да тврђење важи за све сложене бројеве мање од n. Ако је и број n сложен број, тада постоји цео број c такав да је 1<c<n, c|n (ово последње читамо "c дели n", што значи да је број n дељив бројем c). Означимо са m најмањи од поменутих бројева n. Такав 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=\prod_{i=1}^kp_i^{\alpha_i}, где је p_1<p_2<...<p_k,\; \alpha_i>0,\; i=1,2,...,k. Такво представљање називамо канонски облик броја n.
Теорема 2
Сваки природан број има јединствен канонски облик.
Доказ
На основу теореме 1 канонско представљање постоји, а канонски облик простог броја је, очигледно, јединствен. За остале бројеве, доказ изводимо свођењем на контрадикцију. Претпоставимо да постоји природан број који се може представити у канонском облику на два различита начина. Нека је n најмањи такав број n = p1p2...pk = q1q2...qm. Нити један од бројева p не може се појавити у обе канонске репрезентације броја n због претпоставке о минималности n. Бројеве је увек могуће поредати по величини и рецимо p_1\le p_2\le ...\le p_k, \; q_1\le q_2 \le ... \le q_m. За просте факторе p1 и q1 важи p_1 \ne q_1, па можемо узети да је p1 < q1. Нека је u = p1q2...qm. Из u,p1 | n следи (nu), где је nu = (q1p1)q2...qm > 1. Дакле број n-u може се написати у облику nu = p1t1...th, где су ti прости бројеви, за i = 1,2,...,h. Међутим, из q1p1 > 1 повлачи растављање на просте факторе, на пример q1p1 = r1r2...rs, па следи другачији запис броја nu = r1r2...rsq...qm, где нема простог фактора p1. То произилази из p_1\ne q_i,i=1,2,...,m, и са друге стране p_1\ne r_j, j=1,2,...,s, јер p1 није делитељ од q1p1. Дакле број n-u има две различите факторизације, јер само једна од њих садржи прост фактор p1. То важи и у случају када је q1p1 = 1. Међутим, 1 < nu < n, а то је у контрадикцији са претпоставком о минималности броја n. Дакле, не постоји цео број већи од 1 који се може на два начина представити у канонском облику. Крај доказа.


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

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

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

[уреди] Види још