Прости бројеви
А
Ако је [latex]n>1[/latex], онда број [latex]n[/latex] има бар два делиоца: [latex]1\, |\, n[/latex] и [latex]n\, |\, n[/latex]. Неки бројеви имају само ова два делиоца. Такви су, на пример, [latex]2,3,5,7,11,13,17,19.[/latex]
Природни бројеви већи од [latex]1[/latex] који имају тачно два делиоца, број [latex]1[/latex] и сам тај број, јесу прости бројеви. Природни бројеви већи од [latex]1[/latex] који имају више од два делиоца јесу сложени бројеви.
Ако је [latex]n[/latex] сложен број, тада се сви његови делиоци различити од [latex]1[/latex] и [latex]n[/latex] називају прави делиоци броја [latex]n[/latex]. Ако је [latex]d[/latex] било који прави делилац сложеног броја [latex]n[/latex], онда је [latex]1<d<n[/latex]. Одавде закључујемо да је сваки сложен број производ нека своја два права делиоца.
теорема
Сваки природан број већи од [latex]1[/latex] има делиоца који је прост број.
Уместо детаљног доказа наводимо поједностављено објашњење претходног тврђења. Нека је [latex]n[/latex] произвољан природан број.
• Ако је број [latex]n[/latex] прост, онда је он сам свој прост делилац.
• Ако је [latex]n[/latex] сложен број, онда има праве делиоце. У случају да је неки прави делилац [latex]a[/latex] броја [latex]n[/latex] сложен, онда [latex]a[/latex] такође има правог делиоца [latex]b[/latex], који је истовремено и прави делилац полазног броја [latex]n[/latex]. Даље, ако је сложен, онда је прави делилац [latex]c[/latex] броја [latex]b[/latex] такође прави делилац броја [latex]n[/latex]. Поступак издвајања правих делилаца [latex](a,b,c[/latex] итд.[latex])[/latex] броја [latex]n[/latex] некада се мора завршити. То значи да ћемо у неком кораку доћи до простог делиоца броја [latex]n[/latex].
теорема
Простих бројева има бесконачно много.
Доказ.
Претпоставимо супротно, да постоји само коначно много простих бројева. Нека су то бројеви [latex]p_1,p_2,...,p_k[/latex]. Из наведене претпоставке следи да су сложени сви природни бројеви, осим [latex]1[/latex] и наведених простих бројева. Посебно, број [latex]n=p_1p_2...p_k+1[/latex] је сложен, па мора бити дељив неким простим бројем. Међутим, то није могуће, јер се при дељењу броја [latex]n[/latex] било којим од простих бројева[latex]p_1,p_2,...,p_k[/latex] добија се остатак [latex]1[/latex].
Дакле, постоји бесконачно много простих бројева.
Ератостеново сито
Ако је [latex]p[/latex] најмањи прост делилац сложеног броја [latex]n[/latex], онда је [latex]p\cdot p\le n[/latex].
Доказ.
Ако је број [latex]n[/latex] сложен, онда бар један његов прави делилац мора бити прост број. Нека је [latex]p[/latex] најмањи прост делилац сложеног броја [latex]n[/latex]. Тада је [latex]n=p\cdot q[/latex], за неки природан број [latex]q[/latex]. Број [latex]q[/latex] је такође делилац броја [latex]n[/latex].
• Ако је број [latex]q[/latex] прост број, онда је [latex]p\le q[/latex], јер је [latex]p[/latex] најмањи прост делилац броја [latex]n[/latex].
• Ако је број [latex]q[/latex] сложен, он има своје просте делиоце, који су истовремено и прости делиоци броја [latex]n[/latex], па нису мањи од [latex]p[/latex]. Дакле, и у овом случају важи [latex]p\le q[/latex].
Из [latex]p\le q[/latex] и [latex]n=p\cdot q[/latex] следи да је [latex]p^2=p\cdot p\le p\cdot q=n.[/latex]
Пример 1. Претходно тврђење је веома значајно и корисно. Применићемо га да на једноставан начин одредимо све просте бројеве прве стотине. Како је [latex]11\cdot11=121[/latex], према претходној теореми закључујемо да је најмањи прост делилац сложених бројева прве стотине неки од бројева [latex]2,3,5[/latex] или [latex]7[/latex]. То значи да ако неки двоцифрен број није дељив бројевима[latex]2,3,5[/latex] или [latex]7[/latex], онда он није сложен, па је самим тим прост.
Лево су записани сви природни бројеви прве стотине. Поступно ћемо прецртавати све бројеве који нису прости. Број [latex]1[/latex] није прост, и прво њега прецртавамо. Број [latex]2[/latex] је прост. Њега заокружујемо, а прецртавамо све садржаоце броја [latex]2[/latex]. После броја [latex]2[/latex], први непрецртани број јесте прост број [latex]3[/latex]. Њега заокружујемо и прецртавамо све садржаоце броја [latex]3[/latex]. Затим заокружујемо прост број [latex]5[/latex] и прецртавамо све његове садржаоце. Заокружујемо и број [latex]7[/latex] и прецртавамо све његове садржаоце.
На овај начин, прецртали смо све бројеве прве стотине који су дељиви неким од бројева [latex]2,3,5[/latex] или [latex]7[/latex], тј. све сложене бројеве.
Заокруживањем свих непрецртаних бројева издвајамо све просте бројеве прве стотине: [latex]2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97[/latex].
Поступак описан у претходном примеру се може применити за одређивање свих простих бројева који су мањи од неког унапред задатог броја. Поступак се назива Ератостеново сито по старогрчком математичару Ератостену, који је живео у III веку пре нове ере. Ератостен је први издвајао („просејавао”) просте бројеве међу природним бројевима.
Да ли je неки број [latex]n[/latex] сложен или прост испитујемо на следећи начин:
[latex]1)[/latex] прво одредимо све просте бројеве [latex]p[/latex] за које важи [latex]p^2\le n[/latex];
[latex]2)[/latex] затим за сваки прост број, одређен у кораку [latex]1)[/latex], проверавамо да ли он дели [latex]n[/latex].
Ако у кораку [latex]2)[/latex] нађемо прост број који дели [latex]n[/latex], онда је [latex]n[/latex] сложен. У супротном, [latex]n[/latex] је прост.
Пример 2. У примеру користимо табелу квадрата првих петнаест простих бројева.
Да ли је [latex]457[/latex] прост или сложен број?
Користећи претходну табелу, уочавамо да је [latex]23^2=529>457[/latex]. Зато испитујемо да ли је [latex]457[/latex] дељив неким од простих бројева [latex]2,3,5,7,11,13,17,19[/latex]:
[latex]2\nmid457[/latex], [latex]3 \nmid 457[/latex],
[latex]5\nmid457[/latex], [latex]7\nmid457[/latex] [latex](457=7\cdot65+2)[/latex],
[latex]11\nmid 457[/latex] [latex](457=11\cdot41+6)[/latex], [latex]13\nmid 457[/latex] [latex](457=13\cdot35+2)[/latex],
[latex]17 \nmid457 [/latex] [latex](457=17\cdot26+15)[/latex], [latex]19\nmid 457[/latex] [latex](457=19\cdot24+1)[/latex].
Дакле, [latex]457[/latex] је прост број.
Да ли је [latex]299[/latex] прост или сложен број?
Како је [latex]19^2=361>299[/latex], довољно је испитати да ли је [latex]299[/latex] дељив неким од простих бројева [latex]2, 3, 5, 7, 11, 13, 17[/latex]:
[latex]2\nmid 299[/latex] , [latex]3\nmid 299[/latex] ,
[latex]5\nmid 299[/latex] , 7[latex]\nmid [/latex] 299 (299 = 7 · 42 + 5),
[latex]11\nmid 299[/latex] [latex](299=11\cdot27+2)[/latex], [latex]13\, |\, 299[/latex] [latex](299=13\cdot23+0)[/latex].
Дакле, [latex]13\, |\, 299[/latex], одакле следи да је [latex]299[/latex] сложен број [latex](299=13\cdot23)[/latex].
Ератостеново сито је заправо поступак трагања за најмањим простим делиоцем датог броја. Када неки сложен број поделимо његовим најмањим простим делиоцем, добијени количник такође има најмањи прост делилац. Настављајући овај поступак, тј. делећи сваки добијени количник његовим најмањим простим делиоцем, напослетку ћемо добити количник [latex]1[/latex]. Производ свих простих бројева, којима смо делили количнике, једнак је полазном броју. Поступак којим дати број представљамо као производ простих бројева назива се растављање на просте чиниоце.
Основна теорема аритметике
Сваки природан број већи од [latex]1[/latex] може се представити као производ простих бројева.
Основну теорему аритметике можемо формулисати и на следећи начин: за сваки природан број [latex]n[/latex] постоје јединствени прости бројеви [latex]p_1,p_2,...,p_k,p_1<p_2<...<p_k[/latex], и јединствени природни бројеви [latex]\alpha _1,\alpha _2,...\alpha _k[/latex] такви да је [latex]n=p^{\alpha_1}_1p^{\alpha_1}_1...p^{\alpha_k}_k[/latex]. Производ [latex]p^{\alpha _1}_1p^{\alpha _1}_1...p^{\alpha _k}_k[/latex] назива се канонска факторизација броја [latex]n[/latex]. На пример, растављањем броја [latex]588[/latex] на просте чиниоце долазимо до канонске факторизације овог броја: [latex]588=2^2\cdot3\cdot7^2[/latex].
Помоћу канонских факторизација датих природних бројева једноставно се одређује њихов највећи заједнички делилац и најмањи заједнички садржалац. Највећи заједнички делилац смо дефинисали у претходној лекцији.
Дефиниција
Најмањи заједнички садржалац бројева [latex]a[/latex] и [latex]b[/latex] јесте најмањи природан број који је дељив и бројем [latex]a[/latex] и бројем [latex]b[/latex]. Најмањи заједнички садржалац бројева [latex]a[/latex] и [latex]b[/latex] означавамо НЗС[latex](a, b)[/latex].
Пример 3. Један од начина да се одреде НЗД[latex](a,b)[/latex] и НЗС[latex](a,b)[/latex], природних бројева [latex]a[/latex] и [latex]b[/latex], јесте да се сваки од њих растави на просте чиниоце.
Највећи заједнички делилац је производ простих чинилаца који се јављају у растављањима оба броја, при чему се сваки од тих чинилаца узима онолико пута колико се највише садржи у оба броја.
Најмањи заједнички садржалац је производ простих чинилаца који се јављају у растављању бар једног од тих бројева, при чему се сваки чинилац узима онолико пута колико се највише садржи у једном од тих бројева.
Основне идеје из претходног примера можемо уопштено приказати. Нека су [latex]a[/latex] и [latex]b[/latex] било који природни бројеви. Издвојимо просте бројеве који се појављују у канонској факторизацији бар једног од бројева [latex]a[/latex] или [latex]b[/latex]: нека су то прости бројеви [latex]p_1,p_2,...,p_m[/latex]. Међу издвојеним простим бројевима налазе се сви прости чиниоци броја [latex]a[/latex] [latex]([/latex]могуће и они прости бројеви који не деле [latex]a[/latex], већ само деле [latex]b)[/latex]. Узимајући у обзир једнакост [latex]p^0=1[/latex], за било који природан број [latex]p[/latex], закључујемо да за неке ненегативне целе бројеве [latex]\alpha _1,\alpha _2,...,\alpha _m[/latex] важи [latex]a=p^{\alpha_1}_1p^{\alpha_1}_2...p^{\alpha_m}_m[/latex]. Наравно, ако неки прост број [latex]p_i[/latex] не дели [latex]a[/latex], онда је [latex]\alpha_i=0[/latex]. На исти начин закључујемо да постоје ненегативни цели бројеви [latex]\beta _1,\beta _2,...,\beta _m[/latex] важи [latex]b=p^{\beta_1}_1p^{\beta_1}_2...p^{\beta_m}_m[/latex]. Нека је [latex]max\{\alpha,\beta\}[/latex] једнако [latex]\alpha[/latex] ако је [latex]\alpha>\beta[/latex], односно [latex]\beta[/latex] ако је [latex]\alpha\le\beta[/latex]:
Слично уводимо [latex]min\{\alpha,\beta\}[/latex]:
Користећи уведене ознаке, имамо:
[latex]НЗД(a,b)=p^{min\{\alpha_1,\beta_1\}}_1p^{min\{\alpha_2,\beta_2\}}_2...p^{min\{\alpha_m,\beta_m\}}_m[/latex] и
[latex]НЗС(a,b)=p^{max\{\alpha_1,\beta_1\}}_1p^{max\{\alpha_2,\beta_2\}}_2...p^{max\{\alpha_m,\beta_m\}}_m[/latex].
Пример 4. Ако једнакости [latex]126 = 2 ·3^2· 7[/latex] и [latex]315 =3^2· 5 · 7[/latex] запишемо у облику [latex]126 =2^1·3^2·5^0·7^1[/latex] и [latex]315 =2^0·3^2·5^1·7^1[/latex], имамо
[latex]НЗД(126,315)=2^{min\{1,0\}}\cdot3^{min\{2,2\}}\cdot5^{min\{0,1\}}\cdot7^{min\{1,1\}}[/latex]
[latex]=2^0·3^2·5^0·7^1= 63[/latex]
[latex]НЗС(126,315)=2^{max\{1,0\}}\cdot3^{max\{2,2\}}\cdot5^{max\{0,1\}}\cdot7^{max\{1,1\}}[/latex]
[latex]=2^1·3^2·5^1·7^1= 630[/latex]
теорема
За свака два природна броја [latex]a[/latex] и [latex]b[/latex] важи НЗД[latex](a,b)\cdot[/latex]НЗС[latex](a,b)=a\cdot b[/latex].
Доказ.
Нека су [latex]p_1,p_2,...,p_m[/latex] прости бројеви који се појављују у канонској факторизацији бар једног од бројева [latex]a[/latex] или [latex]b[/latex]. Постоје ненегативни цели бројеви [latex]\alpha _1,\alpha _2,...,\alpha _m[/latex] и[latex]\beta _1,\beta _2,...,\beta _m[/latex] такви да је [latex]a=p^{\alpha _1}_1p^{\alpha _1}_2...p^{\alpha _m}_m[/latex] и [latex]b=p^{\beta _1}_1p^{\beta _1}_2...p^{\beta _m}_m[/latex].
Користећи очигледну једнакост [latex]max\{\alpha,\beta\}+min\{\alpha,\beta\}=\alpha+\beta[/latex]
добијамо:
[latex]НЗД(a,b)\cdotНЗС(a,b)[/latex]
[latex]=p^{min\{\alpha_1,\beta_1\}}_1...p^{min\{\alpha_m,\beta_m\}}_m\cdot p^{max\{\alpha_1,\beta_1\}}_1...p^{max\{\alpha_m,\beta_m\}}_m[/latex]
[latex]=p^{min\{\alpha_1,\beta_1\}+max\{\alpha_1,\beta_1\}}_1...p^{min\{\alpha_m,\beta_m\}+max\{\alpha_m,\beta_m\}}_m[/latex]
[latex]=p^{\alpha _1+\beta _1}_1...p^{\alpha _m+\beta _m}_m[/latex]
[latex]=(p^{\alpha _1}_1p^{\alpha _1}_2...p^{\alpha _m}_m)·(p^{\beta _1}_1p^{\beta _1}_2...p^{\beta _m}_m)=a·b[/latex]