Najveći zajednički djelitelj brojeva

Zajednički djeljitelj brojeva a i b je prirodni broj k koji zadovoljava uslov k/a i k/ b. Najveći zajednički djeljitelj brojeva a i b je najveći od brojeva zajedničkih djelitelja. Označava se sa (a ,b) ili NZS(a, b)

Uzajamno prosti brojevi su brojevi a, b koji zadovoljavaju uslov NZD(a, b) = 1 NZD(8,15) = 1 NZD(4, 40) = 4

Teorema 1

Najveći zajednički djeljitelj dva prirodna broja je jedinstven

Teorema 2

Ako je ${\displaystyle c}$ najveći zajednički djelilac perirodnih brojeva ${\displaystyle a}$ i ${\displaystyle b}$, onda postojie cijeli brojevi ${\displaystyle x}$ и ${\displaystyle y}$ takvi da je ${\displaystyle xa+yb=c.}$

Теорема 3:

• Ako je k>0, onda je NZD(ka,kb)=kNZD(a,b).
• Ako je a=bq и b ≥ 0, onda je NZD(a,b)=b.
• Ako je q|ab i q i b prosti brojevi tј. NZD(b,q)=1, onda je а q|a.
• Ako je a=bq+r, onda je NZD(a,b)=NZD(b,r).

Теорема 4

${\displaystyle NZD(a_{1},a_{2},...,a_{n})=NZD(NZD(a_{1},a_{2},...,a_{n-1}),a_{n}).}$