Prije nego što prijeđemo na definiciju pojma najvećeg zajedničkog djelitelja (GCD), potrebno je razumjeti što je zajednički djelitelj općenito.
Poznato je da cijeli broj može imati više djelitelja. Zanima nas istovremeni pristup njima od strane više cijelih brojeva. Zajedničkim djeliteljem nekoliko cijelih brojeva smatramo broj koji može djelovati kao djelitelj za svaki broj iz navedenog niza.
Na primjer, brojevi 8 i 12 imaju sljedeće zajedničke djelitelje: 1 i 4. To se lako može provjeriti pisanjem matematičkih izraza: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
Treba napomenuti da svaki broj u početku ima najmanje dva zajednička djelitelja: svaki je broj djeljiv sam sa sobom bez ostatka, a također je djeljiv s 1.
Određivanje najvećeg zajedničkog djelitelja
Najveći zajednički djelitelj (GCD) dva prirodna broja je najveći od prirodnih brojeva kojima možemo podijeliti dva naša broja. Ako je vrijednost najvećeg zajedničkog djelitelja dvaju prirodnih brojeva 1, tada te brojeve nazivamo međusobno prostima.
Za dva broja a i b, najveći zajednički djelitelj je broj kojim se a i b mogu podijeliti bez ostatka. Ovaj izraz je napisan na sljedeći način: gcd (a, b) = c.
Drugi način za pisanje GCD: (a, b) = c. Međutim, u većini slučajeva koristi se prva opcija.
Tako, na primjer, brojevi 4 i 16 imaju najveći zajednički djelitelj jednak 4. Zapišimo: gcd (4, 16) = 4.
Opišimo kako smo došli do ovog rezultata:
- Ispisali smo sve djelitelje broja 4. Dobili smo: 4, 2, 1.
- Potom smo obojali sve djelitelje broja 16. Dobili smo: 16, 8, 4, 2, 1.
- Odabrali smo djelitelje koji su zajednički i za 4 i za 16. Dobili smo: 4, 2, 1.
- Od dobivenih zajedničkih djelitelja odabran je najveći. Ovo je 4.
- Dobijamo odgovor: za brojeve 4 i 16 GCD je 4.
Slično, možete pronaći GCD za tri ili više cijelih brojeva. U ovom slučaju, to će biti najveći cijeli broj kojim možete podijeliti sve brojeve iz predloženog niza.
Tako će, na primjer, najveći djelitelj za cijele brojeve 6, 12, 18, 42 biti broj 6, odnosno gcd (6, 12, 18, 42) = 6. Odgovor je dobiven korištenjem algoritma slično gore opisanom - za brojeve iz niza redom su ispisani svi djelitelji, nakon čega su odabrani najveći od njih.
GCD svojstva
Najveći zajednički djelitelj ima niz svojstava koja će biti relevantna za GCD pozitivnih cijelih brojeva s djeliteljima većim od nule.
Svojstvo 1
Od promjene mjesta brojeva, konačna vrijednost GCD-a se neće promijeniti. Ovu izjavu možete napisati ovako:
- gcd(a, b) = gcd(b, a).
Svojstvo 2
Ako je a djeljiv s b, tada je skup zajedničkih djelitelja od a i b isti kao skup djelitelja od b. Napisano ovako:
- gcd(a, b) = b.
Dokazano svojstvo najvećeg djelitelja može se upotrijebiti za pronalaženje gcd dva broja kada je jedan od njih djeljiv s drugim. U ovom slučaju GCD je jednak jednom od ovih brojeva, s kojim je djeljiv drugi broj.
Na primjer:
- gcd(12, 4) = 4.
Slično:
- gcd(10, 1) = 1.
Svojstvo 3
Ako je a = bq + c, gdje su a, b, c i q cijeli brojevi, tada je skup zajedničkih djelitelja a i b isti kao skup zajedničkih djelitelja b i c.
Jednakost gcd (a, b) = gcd (b, c) postaje važeća.
Svojstvo 4
Izraz gcd(ma, mb) = m ⋅ gcd(a, b) je istinit pod uvjetom da je m bilo koji prirodni broj.
Svojstvo 5
Recimo da je p bilo koji zajednički djelitelj a i b.
Onda:
- gcd(a / p, b / p) = gcd(a, b) / p.
Ako je p = gcd(a, b), dobivamo:
- gcd (a / gcd (a, b), b / gcd (a, b)) = 1,
Dakle, brojevi a / gcd (a, b) i b / gcd (a, b) su prosti.
Svojstvo 6
Bilo koja dva broja imaju barem jedan zajednički djelitelj - to je broj 1.
Za rad s običnim razlomcima neophodno je poznavanje teorijskih temelja GCD koncepta, kao i praktične vještine u njegovom definiranju. Osim toga, GCD je usko povezan s drugom matematičkom jedinicom - najmanjim zajedničkim djeliteljem. Obje se definicije obično proučavaju kao dio standardnog školskog programa.
