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

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

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

1200 = 24 × 31 × 52 = 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 = ...

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

Прости бројеви, односно прим-бројеви су они који имају само два тачна делиоца: јединицу и самог себе. То је случај са 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=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.\, Крај доказа.

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