Најважније из лекције
- Дељење са остатком: Сваки цео број \( a \) се може јединствено записати као \( a = q \cdot b + r \), где је \( 0 \le r < |b| \).
- Релација дељивости (\( b \mid a \)): Број \( a \) је дељив бројем \( b \) ако је остатак при дељењу 0 (\( a = q \cdot b \)).
- Облик броја: Бројеви се могу класификовати према остатку. На пример, парни бројеви су облика \( 2q \), а непарни \( 2q+1 \).
- Еуклидов алгоритам: Ефикасан метод за проналажење највећег заједничког делиоца (НЗД) узастопним дељењем делиоца претходним остатком док остатак не буде 0.
Природни бројеви: \( \mathbb{N} = \{1, 2, 3, ...\} \)
Природни бројеви са нулом: \( \mathbb{N}_0 = \{0, 1, 2, 3, ...\} \)
Цели бројеви: \( \mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ...\} \)
Природни бројеви са нулом: \( \mathbb{N}_0 = \{0, 1, 2, 3, ...\} \)
Цели бројеви: \( \mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ...\} \)
Скуп целих бројева \( \mathbb{Z} \) уводи се како би једначине облика \( a + x = b \) увек имале решење.
За свака два цела броја \( a \) и \( b \), при чему је \( b \neq 0 \), постоје јединствени цели бројеви \( q \) и \( r \) такви да важи наведена формула. Број \( q \) се назива количник, а \( r \) је остатак.
\[ a = q \cdot b + r \]
Услов за остатак: \( 0 \le r < |b| \)
Остатак при дељењу \( a \) са \( b \) често се означава као \( a \pmod b \).
Остатак при дељењу неког броја са 2 може бити само 0 или 1. На основу тога, цели бројеви се деле на парне и непарне.
- Парни бројеви: при дељењу са 2 дају остатак 0. Записују се у облику \( 2q \), где је \( q \in \mathbb{Z} \).
- Непарни бројеви: при дељењу са 2 дају остатак 1. Записују се у облику \( 2q + 1 \), где је \( q \in \mathbb{Z} \).
Приликом дељења са 3, могући остаци су 0, 1 или 2. Зато је сваки природан број облика \( 3q \), \( 3q + 1 \) или \( 3q + 2 \).
Пример: Сви бројеви који при дељењу са 5 дају остатак 2 имају облик \( 5q + 2 \). Број 97 је највећи такав број у првој стотини јер је \( 97 = 19 \cdot 5 + 2 \).
Пример: Сви бројеви који при дељењу са 5 дају остатак 2 имају облик \( 5q + 2 \). Број 97 је највећи такав број у првој стотини јер је \( 97 = 19 \cdot 5 + 2 \).
Цео број \( a \) је дељив целим бројем \( b \ (b \neq 0) \), ако постоји цео број \( q \) такав да је \( a = q \cdot b \). Ово значи да је остатак при дељењу једнак нули.
Ознака: \( b \mid a \) (Чита се: "\( b \) дели \( a \)" или "\( a \) је дељиво са \( b \)").
Тада је \( b \) делилац броја \( a \), а број \( a \) је садржалац броја \( b \).
Тада је \( b \) делилац броја \( a \), а број \( a \) је садржалац броја \( b \).
Основне особине релације дељивости:
- Ако \( a \mid b \), онда \( a \mid bc \), за свако \( c \in \mathbb{Z} \ (a \neq 0) \).
- Ако \( a \mid b \) и \( b \mid c \), онда \( a \mid c \ (a, b \neq 0) \).
- Ако \( a \mid b \) и \( a \mid c \), онда \( a \mid xb + yc \), за све \( x, y \in \mathbb{Z} \ (a \neq 0) \).
Последица: Ако \( a \mid b \) и \( a \mid c \), онда \( a \mid b + c \) и \( a \mid b - c \). - Ако \( a \mid b \) и \( b \mid a \), онда \( a = b \) или \( a = -b \ (a, b \neq 0) \).
- Ако су \( a, b \ge 1 \) и \( a \mid b \), онда је \( a \le b \).
Највећи заједнички делилац (НЗД) бројева \( a \) и \( b \) јесте највећи природан број који дели и број \( a \) и број \( b \).
Теорема за Еуклидов алгоритам:
За све природне бројеве \( a \) и \( b \):
1) Ако \( b \mid a \), онда је \( \text{НЗД}(a, b) = b \).
2) \( \text{НЗД}(a, b) = \text{НЗД}(b, a \pmod b) \).
За све природне бројеве \( a \) и \( b \):
1) Ако \( b \mid a \), онда је \( \text{НЗД}(a, b) = b \).
2) \( \text{НЗД}(a, b) = \text{НЗД}(b, a \pmod b) \).
Да би се нашао НЗД два броја:
- Већи број се подели мањим и нађе се остатак.
- Претходни делилац се сада дели тим остатком.
- Поступак се понавља све док остатак не буде 0. Последњи делилац (различит од нуле) је тражени НЗД.
Одредимо \( \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 \).
Задаци за вежбање
Лак: Одреди количник \( q \) и остатак \( r \) при дељењу броја 28 бројем 6.
Према формули \( a = q \cdot b + r \):
\( 28 = 4 \cdot 6 + 4 \)
Количник је \( q = 4 \), а остатак је \( r = 4 \).
\( 28 = 4 \cdot 6 + 4 \)
Количник је \( q = 4 \), а остатак је \( r = 4 \).
Средњи: Колико има природних бројева мањих или једнаких 50 који при дељењу са 4 дају остатак 3?
Бројеви који при дељењу са 4 дају остатак 3 су облика \( 4q + 3 \), где је \( q \in \mathbb{N}_0 \).
Тражимо оне за које важи: \( 4q + 3 \le 50 \)
\( 4q \le 47 \)
\( q \le 11 \) (пошто је \( q \) цео број)
Дакле, \( q \) може узети вредности од 0 до 11 (\( q \in \{0, 1, 2, ..., 11\} \)).
Укупно има 12 таквих бројева. (То су бројеви: 3, 7, 11, 15, ..., 47).
Тражимо оне за које важи: \( 4q + 3 \le 50 \)
\( 4q \le 47 \)
\( q \le 11 \) (пошто је \( q \) цео број)
Дакле, \( q \) може узети вредности од 0 до 11 (\( q \in \{0, 1, 2, ..., 11\} \)).
Укупно има 12 таквих бројева. (То су бројеви: 3, 7, 11, 15, ..., 47).
Тежак: Применом Еуклидовог алгоритма одреди \( \text{НЗД}(360, 255) \).
Користимо узастопно дељење:
\( 360 = 1 \cdot 255 + 105 \Rightarrow \text{НЗД}(360, 255) = \text{НЗД}(255, 105) \)
\( 255 = 2 \cdot 105 + 45 \Rightarrow \text{НЗД}(255, 105) = \text{НЗД}(105, 45) \)
\( 105 = 2 \cdot 45 + 15 \Rightarrow \text{НЗД}(105, 45) = \text{НЗД}(45, 15) \)
\( 45 = 3 \cdot 15 + 0 \)
Последњи делилац (када је остатак 0) је 15.
Одговор: \( \text{НЗД}(360, 255) = 15 \).
\( 360 = 1 \cdot 255 + 105 \Rightarrow \text{НЗД}(360, 255) = \text{НЗД}(255, 105) \)
\( 255 = 2 \cdot 105 + 45 \Rightarrow \text{НЗД}(255, 105) = \text{НЗД}(105, 45) \)
\( 105 = 2 \cdot 45 + 15 \Rightarrow \text{НЗД}(105, 45) = \text{НЗД}(45, 15) \)
\( 45 = 3 \cdot 15 + 0 \)
Последњи делилац (када је остатак 0) је 15.
Одговор: \( \text{НЗД}(360, 255) = 15 \).
