Најважније из лекције
Дељивост: Број \( a \) се може представити као \( a = qb + r \), \( 0 \le r < |b| \). Ако је \( r = 0 \), онда \( b \mid a \).
Факторизација: Сваки број се може јединствено раставити на просте чиниоце (\( n = p_1^{\alpha_1} p_2^{\alpha_2} ... \)).
НЗД и НЗС: Везани су формулом \( \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = a \cdot b \). Еуклидов алгоритам је ефикасан метод за проналажење НЗД.
Бројевне базе: Број може бити записан помоћу степена неке базе \( b \). Из декадног у базу \( b \) преводи се узастопним дељењем, а из базе \( b \) у декадни рачунањем полинома.
Факторизација: Сваки број се може јединствено раставити на просте чиниоце (\( n = p_1^{\alpha_1} p_2^{\alpha_2} ... \)).
НЗД и НЗС: Везани су формулом \( \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = a \cdot b \). Еуклидов алгоритам је ефикасан метод за проналажење НЗД.
Бројевне базе: Број може бити записан помоћу степена неке базе \( b \). Из декадног у базу \( b \) преводи се узастопним дељењем, а из базе \( b \) у декадни рачунањем полинома.
Скуп природних бројева означавамо са \( \mathbb{N} \). Ако му додамо нулу, добијамо скуп \( \mathbb{N}_0 = \{0, 1, 2, 3, ...\} \). Природни бројеви, нула и негативни цели бројеви образују скуп целих бројева \( \mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\} \).
Теорема о дељењу са остатком: За свака два цела броја \( a \) и \( b \) (\( b \neq 0 \)), постоје јединствени цели бројеви \( q \) (количник) и \( r \) (остатак) такви да је:
\[ a = q \cdot b + r \quad \text{и} \quad 0 \le r < |b| \]
Остатак при дељењу неког броја увек мора бити већи или једнак нули и строго мањи од апсолутне вредности делиоца!
У зависности од остатка при дељењу са 2, бројеви се деле на парне (облика \( 2q \), остатак 0) и непарне (облика \( 2q + 1 \), остатак 1).
Ако је остатак при дељењу броја \( a \) бројем \( b \) једнак нули, кажемо да \( b \) дели број \( a \), односно да је \( a \) дељиво са \( b \).
Ознака за релацију дељивости је \( b \mid a \). Чита се "\( b \) дели \( a \)". Број \( b \) је делилац, а \( a \) је садржалац.
Основне особине дељивости:
- Ако \( a \mid b \), онда \( a \mid bc \) за свако \( c \in \mathbb{Z} \).
- Ако \( a \mid b \) и \( b \mid c \), онда \( a \mid c \).
- Ако \( a \mid b \) и \( a \mid c \), онда \( a \mid (xb + yc) \) за све \( x, y \in \mathbb{Z} \). Као последица, \( a \) дели и њихов збир (\( b+c \)) и њихову разлику (\( b-c \)).
Прости бројеви су природни бројеви већи од 1 који имају тачно два делиоца: број 1 и сам тај број. Бројеви већи од 1 са више од два делиоца су сложени бројеви.
Сваки природан број већи од 1 има делиоца који је прост број, и простих бројева има бесконачно много.
Испитивање да ли је број прост: Да бисмо проверили да ли је број \( n \) прост, довољно је да проверимо да ли је дељив било којим простим бројем \( p \) за који важи \( p^2 \le n \).
Основна теорема аритметике: Сваки природан број већи од 1 може се на јединствен начин представити као производ простих бројева.
Канонска факторизација:
\[ n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot ... \cdot p_k^{\alpha_k} \]
(где су \( p_1 < p_2 < ... < p_k \) прости бројеви, а \( \alpha_1, ..., \alpha_k \) природни бројеви)
Растављање броја 588 на просте чиниоце: \( 588 = 2 \cdot 294 = 2 \cdot 2 \cdot 147 = 2^2 \cdot 3 \cdot 49 = 2^2 \cdot 3 \cdot 7^2 \).
Највећи заједнички делилац (НЗД) је највећи природан број који дели дате бројеве без остатка. Најмањи заједнички садржалац (НЗС) је најмањи природан број који је дељив свим датим бројевима.
Ако је \( \text{НЗД}(a, b) = 1 \), за бројеве \( a \) и \( b \) кажемо да су узајамно прости.
За свака два природна броја \( a \) и \( b \) важи:
\[ \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = a \cdot b \]
Еуклидов алгоритам је поступак за одређивање НЗД два броја узастопним дељењем. Заснива се на правилу: \( \text{НЗД}(a, b) = \text{НЗД}(b, a \pmod b) \), где је \( a \pmod b \) остатак при дељењу \( a \) са \( b \).
Одређивање \( \text{НЗД}(300, 252) \) Еуклидовим алгоритмом:
\( 300 = 1 \cdot 252 + 48 \Rightarrow \text{НЗД}(300, 252) = \text{НЗД}(252, 48) \)
\( 252 = 5 \cdot 48 + 12 \Rightarrow \text{НЗД}(252, 48) = \text{НЗД}(48, 12) \)
\( 48 = 4 \cdot 12 + 0 \Rightarrow \text{НЗД}(48, 12) = 12 \)
Дакле, \( \text{НЗД}(300, 252) = 12 \).
\( 300 = 1 \cdot 252 + 48 \Rightarrow \text{НЗД}(300, 252) = \text{НЗД}(252, 48) \)
\( 252 = 5 \cdot 48 + 12 \Rightarrow \text{НЗД}(252, 48) = \text{НЗД}(48, 12) \)
\( 48 = 4 \cdot 12 + 0 \Rightarrow \text{НЗД}(48, 12) = 12 \)
Дакле, \( \text{НЗД}(300, 252) = 12 \).
Бројеви се могу записивати у различитим позиционим системима (бројевним базама). Декадни систем користи базу 10, док за базу можемо изабрати било који природан број \( b > 1 \).
Запис броја у бази \( b \), означен као \( (c_n ... c_2 c_1 c_0)_b \), преводи се у декадни систем развојем по степенима базе:
\[ a = c_n b^n + ... + c_2 b^2 + c_1 b^1 + c_0 b^0 \]
(где су \( c_i \) цифре мање од \( b \)).
Ако је база већа од 10 (нпр. хексадекадни систем, \( b=16 \)), за цифре веће од 9 користе се слова абецеде: A=10, B=11, C=12, D=13, E=14, F=15.
Број из декадног система преводи се у систем са базом \( b \) узастопним дељењем тог броја базом. Остаци при том дељењу, записани обрнутим редоследом (од последњег ка првом), чине запис броја у тој бази.
Превођење декадног броја 876 у базу \( b=8 \):
\( 876 = 109 \cdot 8 + \mathbf{4} \)
\( 109 = 13 \cdot 8 + \mathbf{5} \)
\( 13 = 1 \cdot 8 + \mathbf{5} \)
\( 1 = 0 \cdot 8 + \mathbf{1} \)
Читајући остатке одоздо нагоре, добијамо: \( 876 = (1554)_8 \).
\( 876 = 109 \cdot 8 + \mathbf{4} \)
\( 109 = 13 \cdot 8 + \mathbf{5} \)
\( 13 = 1 \cdot 8 + \mathbf{5} \)
\( 1 = 0 \cdot 8 + \mathbf{1} \)
Читајући остатке одоздо нагоре, добијамо: \( 876 = (1554)_8 \).
Задаци за вежбање
Лак: Испити да ли је број 97 прост коришћењем правила за најмањи прост делилац.
Да бисмо проверили да ли је 97 прост, довољно је да проверимо дељивост са простим бројевима \( p \) за које важи \( p^2 \le 97 \). То су бројеви 2, 3, 5 и 7 (јер је \( 7^2 = 49 \le 97 \), а \( 11^2 = 121 > 97 \)).
Број 97:
- Није дељив са 2 (непаран је).
- Није дељив са 3 (збир цифара \( 9+7=16 \), није дељиво са 3).
- Није дељив са 5 (не завршава се на 0 или 5).
- Није дељив са 7 (\( 97 : 7 = 13 \) са остатком 6).
Одговор: Пошто није дељив ниједним од ових бројева, број 97 је прост.
Број 97:
- Није дељив са 2 (непаран је).
- Није дељив са 3 (збир цифара \( 9+7=16 \), није дељиво са 3).
- Није дељив са 5 (не завршава се на 0 или 5).
- Није дељив са 7 (\( 97 : 7 = 13 \) са остатком 6).
Одговор: Пошто није дељив ниједним од ових бројева, број 97 је прост.
Средњи: Одреди \( \text{НЗС}(24, 36) \) ако се зна да је њихов Највећи заједнички делилац \( \text{НЗД}(24, 36) = 12 \), користећи теорему о вези НЗД и НЗС.
Према теореми: \( \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = a \cdot b \)
Заменом познатих вредности:
\( 12 \cdot \text{НЗС}(24, 36) = 24 \cdot 36 \)
\( 12 \cdot \text{НЗС}(24, 36) = 864 \)
\( \text{НЗС}(24, 36) = 864 : 12 \)
\( \text{НЗС}(24, 36) = 72 \)
Одговор: Најмањи заједнички садржалац је 72.
Заменом познатих вредности:
\( 12 \cdot \text{НЗС}(24, 36) = 24 \cdot 36 \)
\( 12 \cdot \text{НЗС}(24, 36) = 864 \)
\( \text{НЗС}(24, 36) = 864 : 12 \)
\( \text{НЗС}(24, 36) = 72 \)
Одговор: Најмањи заједнички садржалац је 72.
Тежак: Користећи Еуклидов алгоритам, одреди \( \text{НЗД}(420, 154) \).
Примењујемо узастопно дељење:
\( 420 = 2 \cdot 154 + 112 \)
\( 154 = 1 \cdot 112 + 42 \)
\( 112 = 2 \cdot 42 + 28 \)
\( 42 = 1 \cdot 28 + 14 \)
\( 28 = 2 \cdot 14 + 0 \)
Последњи делилац при којем је остатак 0 је 14.
Одговор: \( \text{НЗД}(420, 154) = 14 \).
\( 420 = 2 \cdot 154 + 112 \)
\( 154 = 1 \cdot 112 + 42 \)
\( 112 = 2 \cdot 42 + 28 \)
\( 42 = 1 \cdot 28 + 14 \)
\( 28 = 2 \cdot 14 + 0 \)
Последњи делилац при којем је остатак 0 је 14.
Одговор: \( \text{НЗД}(420, 154) = 14 \).
Тежак: Преведи број \( (2A5)_{16} \) из хексадекадног система (база 16) у декадни систем. Затим декадни број 45 преведи у бинарни систем (база 2).
1. Превођење у декадни систем: У бази 16, слово A има вредност 10.
\( (2A5)_{16} = 2 \cdot 16^2 + 10 \cdot 16^1 + 5 \cdot 16^0 \)
\( = 2 \cdot 256 + 10 \cdot 16 + 5 \cdot 1 \)
\( = 512 + 160 + 5 = 677 \)
2. Превођење у бинарни систем (узастопно дељење са 2):
\( 45 = 22 \cdot 2 + \mathbf{1} \)
\( 22 = 11 \cdot 2 + \mathbf{0} \)
\( 11 = 5 \cdot 2 + \mathbf{1} \)
\( 5 = 2 \cdot 2 + \mathbf{1} \)
\( 2 = 1 \cdot 2 + \mathbf{0} \)
\( 1 = 0 \cdot 2 + \mathbf{1} \)
Записујемо остатке одоздо нагоре: \( (101101)_2 \).
Одговор: \( (2A5)_{16} = 677 \), а \( 45 = (101101)_2 \).
\( (2A5)_{16} = 2 \cdot 16^2 + 10 \cdot 16^1 + 5 \cdot 16^0 \)
\( = 2 \cdot 256 + 10 \cdot 16 + 5 \cdot 1 \)
\( = 512 + 160 + 5 = 677 \)
2. Превођење у бинарни систем (узастопно дељење са 2):
\( 45 = 22 \cdot 2 + \mathbf{1} \)
\( 22 = 11 \cdot 2 + \mathbf{0} \)
\( 11 = 5 \cdot 2 + \mathbf{1} \)
\( 5 = 2 \cdot 2 + \mathbf{1} \)
\( 2 = 1 \cdot 2 + \mathbf{0} \)
\( 1 = 0 \cdot 2 + \mathbf{1} \)
Записујемо остатке одоздо нагоре: \( (101101)_2 \).
Одговор: \( (2A5)_{16} = 677 \), а \( 45 = (101101)_2 \).
