Најважније из лекције
НЗД (Највећи заједнички делилац): Највећи број који дели све дате бројеве. Рачуна се множењем само заједничких простих чинилаца са најмањим степеном. Пример: \( \text{НЗД}(12, 16) = 4 \).
НЗС (Најмањи заједнички садржалац): Најмањи број који је дељив свим датим бројевима. Рачуна се множењем свих различитих простих чинилаца са највећим степеном. Пример: \( \text{НЗС}(4, 6) = 12 \).
Узајамно прости бројеви: Бројеви за које важи \( \text{НЗД}(a, b) = 1 \).
Еуклидов алгоритам: Поступак узастопног дељења где важи \( \text{НЗД}(a, b) = \text{НЗД}(b, r) \).
Основна веза: \( \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = a \cdot b \).
НЗС (Најмањи заједнички садржалац): Најмањи број који је дељив свим датим бројевима. Рачуна се множењем свих различитих простих чинилаца са највећим степеном. Пример: \( \text{НЗС}(4, 6) = 12 \).
Узајамно прости бројеви: Бројеви за које важи \( \text{НЗД}(a, b) = 1 \).
Еуклидов алгоритам: Поступак узастопног дељења где важи \( \text{НЗД}(a, b) = \text{НЗД}(b, r) \).
Основна веза: \( \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = a \cdot b \).
Највећи заједнички делилац бројева \( a \) и \( b \) јесте највећи природан број који дели и број \( a \) и број \( b \). Означава се са \( \text{НЗД}(a, b) \).
\( \text{НЗД}(a, b) \) је највећи елемент пресека скупова свих делилаца: \( D_a \cap D_b \).
Ако број \( a \) дели број \( b \) (\( a \mid b \)), онда је:
\[ \text{НЗД}(a, b) = a \]
НЗД се одређује као производ заједничких простих чинилаца који се јављају у растављању оба броја, при чему се сваки заједнички чинилац узима са најмањим изложиоцем (онолико пута колико се највише садржи у оба броја).
Одредимо \( \text{НЗД}(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 \]
Одреди највећи природан број \( d \) такав да се при дељењу бројева 205 и 457 са \( d \) добија остатак 1.
Број \( d \) мора без остатка да дели бројеве \( 205 - 1 = 204 \) и \( 457 - 1 = 456 \). Дакле, тражимо \( \text{НЗД}(204, 456) \):
\[ 204 = 2^2 \cdot 3 \cdot 17, \quad 456 = 2^3 \cdot 3 \cdot 19 \]
\[ \text{НЗД}(204, 456) = 2^2 \cdot 3 = 12 \]
Одговор: Тражени број је 12.
Бројеви који немају заједничких простих делилаца називају се узајамно прости бројеви. Њихов највећи заједнички делилац је 1:
\[ \text{НЗД}(a, b) = 1 \]
- Свака два различита проста броја су узајамно проста: \( \text{НЗД}(2, 3) = 1 \), \( \text{НЗД}(11, 13) = 1 \).
- Прост број и сложен број који није дељив тим простим бројем су узајамно прости: \( \text{НЗД}(7, 18) = 1 \).
- За било која два броја \( a \) и \( b \), бројеви \( a : \text{НЗД}(a, b) \) и \( b : \text{НЗД}(a, b) \) увек су узајамно прости.
Еуклидов алгоритам: Нека је \( a = q \cdot b + r \) (\( 0 \le r < b \)). Скуп свих заједничких делилаца бројева \( a \) и \( b \) једнак је скупу свих заједничких делилаца бројева \( b \) и \( r \), одакле следи:
\[ \text{НЗД}(a, b) = \text{НЗД}(b, r) \]
Одредимо \( \text{НЗД}(16, 6) \) применом Еуклидовог алгоритма:
\[ 16 = 2 \cdot 6 + 4 \implies \text{НЗД}(16, 6) = \text{НЗД}(6, 4) \]
\[ 6 = 1 \cdot 4 + 2 \implies \text{НЗД}(6, 4) = \text{НЗД}(4, 2) \]
\[ 4 = 2 \cdot 2 + 0 \implies \text{НЗД}(4, 2) = 2 \]
Дакле, \( \text{НЗД}(16, 6) = 2 \).
Најмањи заједнички садржалац бројева \( a \) и \( b \) јесте најмањи природан број који је дељив и бројем \( a \) и бројем \( b \). Означава се са \( \text{НЗС}(a, b) \).
\( \text{НЗС}(a, b) \) је најмањи елемент пресека скупова свих садржалаца: \( S_a \cap S_b \).
Ако број \( a \) дели број \( b \) (\( a \mid b \)), онда је:
\[ \text{НЗС}(a, b) = b \]
НЗС је производ свих простих чинилаца који се јављају у растављању бар једног од датих бројева, при чему се сваки чинилац узима са највећим изложиоцем са којим се појављује.
Одредимо \( \text{НЗС}(15, 63) \) скраћеним поступком (делимо док на левој страни не остану само јединице):
\[
\begin{array}{cc|c}
15, & 63 & 3 \\
5, & 21 & 3 \\
5, & 7 & 5 \\
1, & 7 & 7 \\
1, & 1 &
\end{array}
\]
\[ \text{НЗС}(15, 63) = 3^2 \cdot 5 \cdot 7 = 315 \]
Одреди најмањи природан број који при дељењу са 4, 8 и 12 даје остатак 3.
Нека је \( n \) тражени број. Број \( n - 3 \) мора бити дељив бројевима 4, 8 и 12, па је најмањи такав број \( \text{НЗС}(4, 8, 12) \):
\[ 4 = 2^2, \quad 8 = 2^3, \quad 12 = 2^2 \cdot 3 \]
\[ n - 3 = \text{НЗС}(4, 8, 12) = 2^3 \cdot 3 = 24 \]
\[ n = 24 + 3 = 27 \]
Одговор: Тражени број је 27.
\[ \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = a \cdot b \]
Производ највећег заједничког делиоца и најмањег заједничког садржаоца два броја једнак је производу та два броја.
Из основне везе следи начин рачунања НЗС преко НЗД:
\[ \text{НЗС}(a, b) = \frac{a \cdot b}{\text{НЗД}(a, b)} \]
Ако су бројеви \( a \) и \( b \) узајамно прости (\( \text{НЗД}(a, b) = 1 \)), тада је:
\[ \text{НЗС}(a, b) = a \cdot b \]
За бројеве 75 и 105 одредити \( \text{НЗС}(75, 105) \) помоћу \( \text{НЗД} \):
\[ 75 = 3 \cdot 5^2, \quad 105 = 3 \cdot 5 \cdot 7 \implies \text{НЗД}(75, 105) = 3 \cdot 5 = 15 \]
\[ \text{НЗС}(75, 105) = \frac{75 \cdot 105}{15} = 75 \cdot 7 = 525 \]
Задаци за вежбање
Задатак 1 (лак): Одреди \( \text{НЗД}(54, 36) \) и \( \text{НЗС}(54, 36) \).
Раставимо бројеве на просте чиниоце:
\[ 54 = 2 \cdot 3^3, \quad 36 = 2^2 \cdot 3^2 \]
Заједнички чиниоци са мањим степеном:
\[ \text{НЗД}(54, 36) = 2 \cdot 3^2 = 2 \cdot 9 = 18 \]
Сви чиниоци са већим степеном:
\[ \text{НЗС}(54, 36) = 2^2 \cdot 3^3 = 4 \cdot 27 = 108 \]
Провера: \( 18 \cdot 108 = 1944 = 54 \cdot 36 \).
Задатак 2 (средњи): Обим предњег точка трактора износи \( 210 \text{ cm} \), а задњег \( 330 \text{ cm} \). Колики је најкраћи пут који трактор треба да пређе да би оба точка направила цео број пуних обртаја?
Најкраћи пут \( s \) представља најмањи заједнички садржалац обима точкова:
\[ s = \text{НЗС}(210, 330) \]
Раставимо бројеве на просте чиниоце:
\[ 210 = 2 \cdot 3 \cdot 5 \cdot 7 \]
\[ 330 = 2 \cdot 3 \cdot 5 \cdot 11 \]
\[ \text{НЗС}(210, 330) = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310 \text{ cm} = 23{,}1 \text{ m} \]
Одговор: Најкраћи пут је \( 2310 \text{ cm} \) (или \( 23{,}1 \text{ m} \)).
Задатак 3 (средњи): За непознате природне бројеве \( a \) и \( b \) познато је: \( \text{НЗД}(a, b) = 12 \), \( \text{НЗС}(a, b) = 72 \) и \( 3 \cdot a = 2 \cdot b \). Одреди бројеве \( a \) и \( b \).
Користимо везу између делиоца и садржаоца:
\[ a \cdot b = \text{НЗД}(a, b) \cdot \text{НЗС}(a, b) = 12 \cdot 72 = 864 \]
Из услова \( 3 \cdot a = 2 \cdot b \) следи \( b = \frac{3a}{2} \). Уврстимо у производ:
\[ a \cdot \frac{3a}{2} = 864 \implies \frac{3a^2}{2} = 864 \implies 3a^2 = 1728 \implies a^2 = 576 \implies a = 24 \]
Затим рачунамо \( b \):
\[ b = \frac{3 \cdot 24}{2} = 36 \]
Одговор: Бројеви су \( a = 24 \) и \( b = 36 \).
Задатак 4 (тежак): Збир два природна броја \( a \) и \( b \) је 84 (\( a + b = 84 \)), а њихов највећи заједнички делилац је 7 (\( \text{НЗД}(a, b) = 7 \)). Одреди све могуће парове бројева \( a \) и \( b \) (уз претпоставку \( a \le b \)).
Пошто је \( \text{НЗД}(a, b) = 7 \), бројеве можемо записати као:
\[ a = 7 \cdot x \quad \text{и} \quad b = 7 \cdot y \]
где су \( x \) и \( y \) узајамно прости природни бројеви (\( \text{НЗД}(x, y) = 1 \)).
Уврстимо у збир:
\[ 7x + 7y = 84 \implies 7(x + y) = 84 \implies x + y = 12 \]
Тражимо парове узајамно простих бројева \( (x, y) \) чији је збир 12 (\( x \le y \)):
- \( x = 1, y = 11 \) (\( \text{НЗД}(1, 11) = 1 \)) \( \implies a = 7 \cdot 1 = 7, \quad b = 7 \cdot 11 = 77 \)
- \( x = 2, y = 10 \) - нису узајамно прости (\( \text{НЗД}(2, 10) = 2 \neq 1 \))
- \( x = 3, y = 9 \) - нису узајамно прости (\( \text{НЗД}(3, 9) = 3 \neq 1 \))
- \( x = 4, y = 8 \) - нису узајамно прости (\( \text{НЗД}(4, 8) = 4 \neq 1 \))
- \( x = 5, y = 7 \) (\( \text{НЗД}(5, 7) = 1 \)) \( \implies a = 7 \cdot 5 = 35, \quad b = 7 \cdot 7 = 49 \)
- \( x = 6, y = 6 \) - нису узајамно прости
