Најважније из лекције
НЗД: Највећи заједнички делилац је највећи број којим се дати бројеви могу поделити без остатка.
Методе тражења: Најпрактичнији начин је истовремено дељење заједничким простим чиниоцима. Алтернатива је Еуклидов алгоритам заснован на правилу \( \text{НЗД}(a, b) = \text{НЗД}(b, r) \).
Узајамно прости бројеви: Ако два броја немају ниједан заједнички прост делилац (тј. НЗД им је 1), називамо их узајамно простим бројевима (нпр. 8 и 15).
Методе тражења: Најпрактичнији начин је истовремено дељење заједничким простим чиниоцима. Алтернатива је Еуклидов алгоритам заснован на правилу \( \text{НЗД}(a, b) = \text{НЗД}(b, r) \).
Узајамно прости бројеви: Ако два броја немају ниједан заједнички прост делилац (тј. НЗД им је 1), називамо их узајамно простим бројевима (нпр. 8 и 15).
Највећи заједнички делилац два или више бројева јесте највећи природан број који дели сваки од тих бројева без остатка.
Означава се са НЗД(\( a, b \)).
Ако један број дели други (тј. \( a \mid b \)), онда је њихов највећи заједнички делилац управо тај мањи број:
\[ \text{НЗД}(a, b) = a \]
Пошто 12 дели 36 без остатка (\( 36 : 12 = 3 \)), важи: \( \text{НЗД}(12, 36) = 12 \).
Одредите НЗД(8, 32) применом правила о дељивости.
Одговор: Пошто је број 32 дељив бројем 8, следи да је \( \text{НЗД}(8, 32) = 8 \).
Најједноставнији поступак за налажење НЗД-а је истовремено растављање датих бројева на заједничке просте чиниоце. Поступак се завршава када бројеви више немају заједничких простих делилаца.
Запишемо бројеве један поред другог и одвојимо их усправном цртом.
Делимо их најмањим заједничким простим бројем.
Понављамо поступак са добијеним количницима све док они имају заједничких делилаца.
НЗД је једнак производу свих простих делилаца са десне стране усправне црте.
Одредимо НЗД(84, 90):
\[
\begin{array}{cc|c}
84, & 90 & 2 \\
42, & 45 & 3 \\
14, & 15 &
\end{array}
\]
Бројеви 14 и 15 више немају заједничких делилаца. Зато је:
\[ \text{НЗД}(84, 90) = 2 \cdot 3 = 6 \]
Одредите НЗД(48, 72, 96).
Истовремено делимо сва три броја заједничким простим чиниоцима:
\[
\begin{array}{ccc|c}
48, & 72, & 96 & 2 \\
24, & 36, & 48 & 2 \\
12, & 18, & 24 & 2 \\
6, & 9, & 12 & 3 \\
2, & 3, & 4 &
\end{array}
\]
Бројеви 2, 3 и 4 немају заједнички делилац (осим 1).
Одговор: \( \text{НЗД}(48, 72, 96) = 2 \cdot 2 \cdot 2 \cdot 3 = 24 \).
Одговор: \( \text{НЗД}(48, 72, 96) = 2 \cdot 2 \cdot 2 \cdot 3 = 24 \).
Бројеви који немају заједничке просте делиоце називају се узајамно прости бројеви. Њихов највећи заједнички делилац је број 1.
Ако су бројеви \( a \) и \( b \) узајамно прости, важи:
\[ \text{НЗД}(a, b) = 1 \]
Бројеви 16 и 75 су узајамно прости јер је \( 16 = 2^4 \), а \( 75 = 3 \cdot 5^2 \). Немају ниједан заједнички прост чинилац. Дакле, НЗД(16, 75) = 1.
Такође, свака два различита проста броја су увек узајамно прости (нпр. НЗД(11, 13) = 1).
Такође, свака два различита проста броја су увек узајамно прости (нпр. НЗД(11, 13) = 1).
Да ли су бројеви 14 и 33 узајамно прости?
Раставимо бројеве на просте чиниоце:
\( 14 = 2 \cdot 7 \)
\( 33 = 3 \cdot 11 \)
Немају заједничких простих делилаца.
Одговор: Да, узајамно су прости, НЗД(14, 33) = 1.
\( 14 = 2 \cdot 7 \)
\( 33 = 3 \cdot 11 \)
Немају заједничких простих делилаца.
Одговор: Да, узајамно су прости, НЗД(14, 33) = 1.
Еуклидов алгоритам је поступак за одређивање НЗД-а два природна броја коришћењем дељења са остатком.
Нека су \( a \) и \( b \) бројеви, а \( r \) остатак при дељењу \( a \) са \( b \). Тада важи:
\[ \text{НЗД}(a, b) = \text{НЗД}(b, r) \]
Одредимо НЗД(16, 6) помоћу Еуклидовог алгоритма:
1. Делимо 16 са 6: \( 16 = 2 \cdot 6 + 4 \) (остатак је 4). Дакле, \( \text{НЗД}(16, 6) = \text{НЗД}(6, 4) \).
2. Делимо 6 са 4: \( 6 = 1 \cdot 4 + 2 \) (остатак је 2). Дакле, \( \text{НЗД}(6, 4) = \text{НЗД}(4, 2) \).
3. Делимо 4 са 2: \( 4 = 2 \cdot 2 + 0 \) (остатак је 0).
Када је остатак 0, НЗД је последњи делилац.
Дакле, \( \text{НЗД}(16, 6) = 2 \).
1. Делимо 16 са 6: \( 16 = 2 \cdot 6 + 4 \) (остатак је 4). Дакле, \( \text{НЗД}(16, 6) = \text{НЗД}(6, 4) \).
2. Делимо 6 са 4: \( 6 = 1 \cdot 4 + 2 \) (остатак је 2). Дакле, \( \text{НЗД}(6, 4) = \text{НЗД}(4, 2) \).
3. Делимо 4 са 2: \( 4 = 2 \cdot 2 + 0 \) (остатак је 0).
Када је остатак 0, НЗД је последњи делилац.
Дакле, \( \text{НЗД}(16, 6) = 2 \).
Задаци за вежбање
Лак: Одредите највећи заједнички делилац бројева 24 и 36.
\[
\begin{array}{cc|c}
24, & 36 & 2 \\
12, & 18 & 2 \\
6, & 9 & 3 \\
2, & 3 &
\end{array}
\]
Одговор: \( \text{НЗД}(24, 36) = 2 \cdot 2 \cdot 3 = 12 \).
Средњи: Да ли су бројеви 28 и 45 узајамно прости? Образложите.
Растављамо бројеве на просте чиниоце:
\( 28 = 2 \cdot 2 \cdot 7 \)
\( 45 = 3 \cdot 3 \cdot 5 \)
Ова два броја немају ниједан заједнички прост чинилац. Њихов једини заједнички делилац је 1.
Одговор: Да, бројеви су узајамно прости јер је НЗД(28, 45) = 1.
\( 28 = 2 \cdot 2 \cdot 7 \)
\( 45 = 3 \cdot 3 \cdot 5 \)
Ова два броја немају ниједан заједнички прост чинилац. Њихов једини заједнички делилац је 1.
Одговор: Да, бројеви су узајамно прости јер је НЗД(28, 45) = 1.
Тежак: Одредите највећи природан број \( d \) такав да се при дељењу бројева 205 и 457 са тим бројем добија остатак 1.
Ако при дељењу са \( d \) бројеви 205 и 457 дају остатак 1, то значи да ће бројеви умањени за 1 бити дељиви бројем \( d \) без остатка.
Тражимо бројеве: \( 205 - 1 = 204 \) и \( 457 - 1 = 456 \).
Број \( d \) је највећи заједнички делилац ових бројева. \[ \begin{array}{cc|c} 204, & 456 & 2 \\ 102, & 228 & 2 \\ 51, & 114 & 3 \\ 17, & 38 & \end{array} \] Број 17 је прост, а 38 није дељиво са 17, па немају више заједничких делилаца.
Одговор: \( d = \text{НЗД}(204, 456) = 2 \cdot 2 \cdot 3 = 12 \).
Тражимо бројеве: \( 205 - 1 = 204 \) и \( 457 - 1 = 456 \).
Број \( d \) је највећи заједнички делилац ових бројева. \[ \begin{array}{cc|c} 204, & 456 & 2 \\ 102, & 228 & 2 \\ 51, & 114 & 3 \\ 17, & 38 & \end{array} \] Број 17 је прост, а 38 није дељиво са 17, па немају више заједничких делилаца.
Одговор: \( d = \text{НЗД}(204, 456) = 2 \cdot 2 \cdot 3 = 12 \).
