Preden nadaljujemo z definicijo koncepta največjega skupnega delitelja (GCD), je treba razumeti, kaj je skupni delitelj na splošno.
Znano je, da ima lahko celo število več deliteljev. Zanima nas hkraten dostop do njih več celih števil. Za skupni delitelj več celih števil štejemo tisto število, ki lahko deluje kot delitelj za vsako število iz navedene serije.
Na primer, števili 8 in 12 imata naslednja skupna delitelja: 1 in 4. To lahko enostavno preverimo s pisanjem matematičnih izrazov: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
Upoštevati je treba, da ima vsako število na začetku vsaj dva skupna delitelja: vsako število je deljivo samo s seboj brez ostanka in je deljivo tudi z 1.
Določanje največjega skupnega delitelja
Največji skupni delitelj (GCD) dveh naravnih števil je največje izmed naravnih števil, s katerim lahko delimo dve svoji števili. Če je vrednost največjega skupnega delitelja dveh naravnih števil enaka 1, potem ti števili pravimo soprosto.
Za dve števili a in b je največji skupni delitelj število, s katerim lahko a in b delimo brez ostanka. Ta izraz je zapisan takole: gcd (a, b) = c.
Drug način za pisanje GCD: (a, b) = c. Vendar se v večini primerov uporabi prva možnost.
Tako imata na primer števili 4 in 16 največji skupni delitelj enak 4. Zapišimo: gcd (4, 16) = 4.
Opišimo, kako smo prišli do tega rezultata:
- Izpisali smo vse delitelje števila 4. Dobili smo: 4, 2, 1.
- Nato smo pobarvali vse delitelje števila 16. Dobili smo: 16, 8, 4, 2, 1.
- Izbrali smo delitelje, ki so skupni za 4 in 16. Dobili smo: 4, 2, 1.
- Iz dobljenih skupnih deliteljev je bil izbran največji. To je 4.
- Dobimo odgovor: za števili 4 in 16 je GCD 4.
Podobno lahko najdete GCD za tri ali več celih števil. V tem primeru bo to največje celo število, s katerim lahko delite vsa števila iz predlagane serije.
Tako bo na primer največji delitelj za cela števila 6, 12, 18, 42 število 6, to je gcd (6, 12, 18, 42) = 6. Odgovor je bil pridobljen z uporabo algoritma podobno kot je opisano zgoraj - za števila iz niza so bili zaporedno izpisani vsi delitelji, nato pa izbrani največji med njimi.
Lastnosti GCD
Največji skupni delitelj ima številne lastnosti, ki bodo pomembne za GCD pozitivnih celih števil z delitelji, večjimi od nič.
Lastnost 1
Če zamenjate mesta številk, se končna vrednost GCD ne bo spremenila. To izjavo lahko zapišete takole:
- gcd(a, b) = gcd(b, a).
Lastnost 2
Če je a deljiv z b, potem je množica skupnih deliteljev a in b enaka množici deliteljev b. Napisano takole:
- gcd(a, b) = b.
Dokazano lastnost največjega delitelja je mogoče uporabiti za iskanje gcd dveh števil, ko je eno od njiju deljivo z drugim. V tem primeru je GCD enak enemu od teh števil, s katerim je deljivo drugo število.
Na primer:
- gcd(12, 4) = 4.
Podobno:
- gcd(10, 1) = 1.
Lastnost 3
Če je a = bq + c, kjer so a, b, c in q cela števila, potem je množica skupnih deliteljev za a in b enaka množici skupnih deliteljev za b in c.
Enakost gcd (a, b) = gcd (b, c) postane veljavna.
Lastnost 4
Izraz gcd(ma, mb) = m ⋅ gcd(a, b) velja pod pogojem, da je m poljubno naravno število.
Lastnost 5
Recimo, da je p poljuben skupni delitelj a in b.
Potem:
- gcd(a / p, b / p) = gcd(a, b) / p.
Če je p = gcd(a, b), dobimo:
- gcd (a / gcd (a, b), b / gcd (a, b)) = 1,
Tako sta števili a / gcd (a, b) in b / gcd (a, b) soprosti.
Lastnost 6
Kateri koli dve števili imata vsaj en skupni delitelj – to je število 1.
Za delo z navadnimi ulomki sta potrebna poznavanje teoretičnih osnov koncepta GCD in praktične veščine njegove definicije. Poleg tega je GCD tesno povezan z drugo matematično enoto - najmanjšim skupnim deliteljem. Obe definiciji se običajno preučujeta kot del standardnega šolskega kurikuluma.
