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

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

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

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

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

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

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

Прости бројеви, односно прим-бројеви су они који имају само два тачна делиоца: јединицу и самог себе. То је случај са 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_10,\; i=1,2,...,k.Такво представљање називамо канонски облик броја n.
Теорема 2
Сваки природан број има јединствен канонски облик.
Доказ
На основу теореме 1 канонско представљање постоји, а канонски облик простог броја је, очигледно, јединствен. За остале бројеве, доказ изводимо свођењем на контрадикцију. Претпоставимо да постоји природан број који се може представити у канонском облику на два различита начина. Нека је n најмањи такав број n=p_1p_2...p_k=q_1q_2...q_m. Ниједан од бројева p не може се појавити у обе канонске репрезентације броја n због претпоставке о минималности n. Бројеве је увек могуће поредати по величини и рецимо p_1\le p_2\le ...\le p_k, \; q_1\le q_2 \le ... \le q_m. За просте факторе p_1 и q_1 важи p_1 \ne q_1, па можемо узети да је p_1 < q_1. Нека је u=p_1q_2...q_m. Из p_1|u,p_1|n следи p_1|(n-u), где је n-u=(q_1-p_1)q_2...q_m>1. Дакле број n-u може се написати у облику n-u=p_1t_1...t_h, где су t_i прости бројеви, за i=1,2,...,h. Међутим, из q_1-p_1>1 повлачи растављање на просте факторе, на пример q_1-p_1=r_1r_2...r_s, па следи другачији запис броја n-u=r_1r_2...r_sq_...q_m, где нема простог фактора p_1. То произилази из p_1\ne q_i,i=1,2,...,m, и са друге стране p_1\ne 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, то су бројеви облика 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}.
Тада је c|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.\, Крај доказа.

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