Најважније из лекције
Заједнички делилац бројева \( a \) и \( b \) јесте природан број који је делилац и броја \( a \) и броја \( b \). Највећи заједнички делилац (НЗД), у ознаци \( D(a, b) \), јесте највећи такав број. НЗД се одређује набрајањем делилаца (пресек скупова \( D_a \cap D_b \)) или, погодније, растављањем бројева на просте чиниоце — НЗД је производ заједничких простих чинилаца. Ако један број дели други, НЗД је мањи од њих \( (D(a,b) = a \) кад \( a \mid b) \). Бројеви су узајамно прости ако је \( D(a, b) = 1 \); суседни природни бројеви су увек узајамно прости: \( D(n, n+1) = 1 \).
Заједнички делилац бројева \( a \) и \( b \) јесте природан број који је истовремено делилац и броја \( a \) и броја \( b \).
Највећи заједнички делилац (НЗД) бројева \( a \) и \( b \), у ознаци \( D(a, b) \), јесте највећи од заједничких делилаца.
\( D_{24} \cap D_{36} = \{1, 2, 3, 4, 6, 12\} \), па је \( D(24, 36) = 12 \).
Поступак:
- Бројеве делимо заједничким простим делиоцима док је могуће.
- НЗД је производ тих заједничких простих чинилаца.
\( D(36, 90) = 2 \cdot 3 \cdot 3 = 18 \).
Ако један број дели други, НЗД је једнак мањем броју: ако \( a \mid b \), онда \( D(a, b) = a \). Слично се одређује и НЗД за три и више бројева.
За два броја кажемо да су узајамно прости ако је њихов највећи заједнички делилац једнак 1, тј. \( D(a, b) = 1 \).
\( D(8, 9) = 1 \), па су 8 и 9 узајамно прости.
За свака два суседна природна броја важи \( D(n, n+1) = 1 \).
Када су бројеви велики, НЗД се може одредити Еуклидовим алгоритмом: НЗД два броја замењује се НЗД-ом мањих бројева, док се поступак не заврши.
\( D(15, 6) = D(6, 9) = 3 \).
