Најважније из лекције
- Прости бројеви имају само два делиоца (1 и себе), док сложени имају више од два. Бројева има бесконачно много и сваки природан број већи од 1 има бар један прост делилац.
- Тестирање простости: Број \( n \) испитујемо тако што проверавамо да ли је дељив простим бројевима \( p \) за које важи \( p^2 \le n \).
- Основна теорема аритметике: Сваки број се може јединствено записати као производ простих чинилаца (нпр. \( 12 = 2^2 \cdot 3 \)).
- Веза НЗД и НЗС: Производ највећег заједничког делиоца и најмањег заједничког садржаоца два броја једнак је производу та два броја: \( НЗД(a, b) \cdot НЗС(a, b) = a \cdot b \).
Природни бројеви већи од 1 који имају тачно два делиоца, број 1 и сам тај број, јесу прости бројеви.
Природни бројеви већи од 1 који имају више од два делиоца јесу сложени бројеви.
Прости бројеви су: 2, 3, 5, 7, 11, 13, 17, 19...
Сложени бројеви су: 4, 6, 8, 9, 10, 12...
Сложени бројеви су: 4, 6, 8, 9, 10, 12...
Сви делиоци сложеног броја \( n \), који су различити од 1 и самог броја \( n \), називају се прави делиоци. Сваки сложен број је производ нека своја два права делиоца.
Сваки природан број већи од 1 има делиоца који је прост број.
Простих бројева има бесконачно много.
Својство најмањег простог делиоца:
Ако је \( p \) најмањи прост делилац сложеног броја \( n \), онда важи \( p \cdot p \le n \) (односно \( p^2 \le n \)).
Ако је \( p \) најмањи прост делилац сложеног броја \( n \), онда важи \( p \cdot p \le n \) (односно \( p^2 \le n \)).
Ако тражимо најмањи прост делилац неког сложеног броја до 100, он мора бити мањи или једнак 10, јер је \( 10 \cdot 10 = 100 \). То значи да ће тај делилац бити један од бројева: 2, 3, 5 или 7.
Ератостеново сито је поступак за одређивање свих простих бројева који су мањи од неког задатог броја тако што се редом прецртавају садржаоци простих бројева (почевши од 2), док непрецртани бројеви остају прости.
Да ли је неки број \( n \) сложен или прост испитујемо у два корака:
Одредимо све просте бројеве \( p \) за које важи \( p^2 \le n \).
За сваки тај прост број проверавамо да ли он дели \( n \). Ако нађемо бар један који га дели, број је сложен. У супротном, број је прост.
Да ли је број 29 прост или сложен?
Прости бројеви за које важи \( p^2 \le 29 \) су 2, 3 и 5 (јер је \( 5^2 = 25 \), а \( 7^2 = 49 > 29 \)).
Број 29 није дељив ни са 2, ни са 3, ни са 5. Дакле, 29 је прост број.
Прости бројеви за које важи \( p^2 \le 29 \) су 2, 3 и 5 (јер је \( 5^2 = 25 \), а \( 7^2 = 49 > 29 \)).
Број 29 није дељив ни са 2, ни са 3, ни са 5. Дакле, 29 је прост број.
Сваки природан број већи од 1 може се представити као производ простих бројева.
Овај поступак дељења сложеног броја његовим најмањим простим делиоцима док се не добије количник 1 назива се растављање на просте чиниоце.
За сваки природан број \( n \) постоји јединствена канонска факторизација:
\[ n = p_1^{\alpha_1} p_2^{\alpha_2} ... p_k^{\alpha_k} \] (где су \( p \) прости бројеви, а \( \alpha \) њихови изложиоци који показују колико пута се тај прост број појављује као чинилац)
\[ n = p_1^{\alpha_1} p_2^{\alpha_2} ... p_k^{\alpha_k} \] (где су \( p \) прости бројеви, а \( \alpha \) њихови изложиоци који показују колико пута се тај прост број појављује као чинилац)
Растављање броја 588:
\( 588 = 2 \cdot 294 \)
\( 294 = 2 \cdot 147 \)
\( 147 = 3 \cdot 49 \)
\( 49 = 7 \cdot 7 \)
Канонска факторизација: \( 588 = 2^2 \cdot 3 \cdot 7^2 \)
\( 588 = 2 \cdot 294 \)
\( 294 = 2 \cdot 147 \)
\( 147 = 3 \cdot 49 \)
\( 49 = 7 \cdot 7 \)
Канонска факторизација: \( 588 = 2^2 \cdot 3 \cdot 7^2 \)
НЗД (Највећи заједнички делилац) је производ заједничких простих чинилаца који се јављају у оба броја, при чему се сваки узима најмање пута колико се јавља (минимум).
НЗС (Најмањи заједнички садржалац) је производ свих простих чинилаца који се јављају у бар једном од бројева, при чему се сваки узима највише пута колико се јавља (максимум).
За свака два природна броја \( a \) и \( b \) важи:
\[ НЗД(a, b) \cdot НЗС(a, b) = a \cdot b \]
Задаци за вежбање
Лак: Разврстај следеће бројеве на просте и сложене: 2, 9, 11, 15, 23.
Прости бројеви: 2, 11, 23 (имају само два делиоца).
Сложени бројеви: 9, 15 (имају више од два делиоца, нпр. 9 је дељиво са 3, а 15 са 3 и 5).
Сложени бројеви: 9, 15 (имају више од два делиоца, нпр. 9 је дељиво са 3, а 15 са 3 и 5).
Средњи: Испитујући дељивост, провери да ли је број 137 прост или сложен.
1. Тражимо просте бројеве \( p \) за које важи \( p^2 \le 137 \). Како је \( 11^2 = 121 \) и \( 13^2 = 169 \), испитујемо просте бројеве до 11: 2, 3, 5, 7, 11.
2. Проверавамо дељивост:
- Није дељив са 2 (није паран).
- Није дељив са 3 (\( 1+3+7=11 \)).
- Није дељив са 5 (не завршава се на 0 или 5).
- Није дељив са 7 (\( 137 : 7 = 19 \) остатак 4).
- Није дељив са 11 (\( 137 : 11 = 12 \) остатак 5).
Пошто није дељив ниједним од њих, број 137 је прост.
2. Проверавамо дељивост:
- Није дељив са 2 (није паран).
- Није дељив са 3 (\( 1+3+7=11 \)).
- Није дељив са 5 (не завршава се на 0 или 5).
- Није дељив са 7 (\( 137 : 7 = 19 \) остатак 4).
- Није дељив са 11 (\( 137 : 11 = 12 \) остатак 5).
Пошто није дељив ниједним од њих, број 137 је прост.
Тежак: Растави бројеве 24 и 36 на просте чиниоце. На основу тога одреди њихов НЗД и НЗС, а затим провери да ли важи теорема \( НЗД(24, 36) \cdot НЗС(24, 36) = 24 \cdot 36 \).
Факторизација:
\( 24 = 2^3 \cdot 3 \)
\( 36 = 2^2 \cdot 3^2 \)
Одређивање НЗД и НЗС:
\( НЗД(24, 36) = 2^2 \cdot 3 = 4 \cdot 3 = 12 \) (узимамо најмање изложиоце)
\( НЗС(24, 36) = 2^3 \cdot 3^2 = 8 \cdot 9 = 72 \) (узимамо највеће изложиоце)
Провера теореме:
\( НЗД \cdot НЗС = 12 \cdot 72 = 864 \)
\( a \cdot b = 24 \cdot 36 = 864 \)
Теорема важи јер је \( 864 = 864 \).
\( 24 = 2^3 \cdot 3 \)
\( 36 = 2^2 \cdot 3^2 \)
Одређивање НЗД и НЗС:
\( НЗД(24, 36) = 2^2 \cdot 3 = 4 \cdot 3 = 12 \) (узимамо најмање изложиоце)
\( НЗС(24, 36) = 2^3 \cdot 3^2 = 8 \cdot 9 = 72 \) (узимамо највеће изложиоце)
Провера теореме:
\( НЗД \cdot НЗС = 12 \cdot 72 = 864 \)
\( a \cdot b = 24 \cdot 36 = 864 \)
Теорема важи јер је \( 864 = 864 \).
