Suurin yhteinen jakaja (GCF) on suurin luku, jolla kaksi tai useampi luku voidaan jakaa. Tämä jättämättä mitään jäämiä.
Toisin sanoen suurin yhteinen jakaja eli GCF on korkein luku, jolla numerosarja voidaan jakaa, jolloin saadaan kokonaisluku.
Jakaja voidaan muodollisesti määritellä numeroksi, joka sisältyy toiseen tarkalleen n kertaa kerralla.
On huomattava, että lukujen, joille GCF lasketaan, on oltava nollia.
Selitämme sitä paremmin, katsotaanpa esimerkkiä. Oletetaan, että meillä on 35 ja 15. Siksi tarkkailemme, mitä kummankin jakajat ovat:
- Jakajat 35 → 35,7,5,1
- Jakajat 15 → 15,5,3,1
Siksi suurin yhteinen tekijä 35 ja 15 on 5.
On syytä mainita, että jos kahden luvun yhteiset jakajat ovat vain 1 ja -1, niitä kutsutaan "toissijaiseksi päällikölle".
Menetelmät suurimman yhteisen jakajan laskemiseksi
Voimme erottaa seuraavat kolme tapaa laskea suurin yhteinen jakaja:
- Päätekijän hajoaminen: Numerot hajotetaan alkulukuiksi. Sitten laskemme GCF: n ottamalla tavalliset luvut pienimpään tehoon. Oletetaan esimerkiksi, että meillä on 216 ja 156:
216/2=108
108/2=54
54/2=27
27/3=9
9/3=3
3/3=1
216=(3^3)*(2^3)
156/2=78
78/2=39
39/3=13
13/13=1
156=13*3*(2^2)
Siksi suurin yhteinen jakaja molempien numeroiden välillä olisi: (2 2) * 3 = 12
Oletetaan, että meillä on kolme elementtiä: 315, 441 ja 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Sitten niiden hajottamisen jälkeen, ottamalla jokaisen jakajan pienimmällä voimallaan, tulos olisi:
GCF = (3 2) * 7 = 63
- Eukleidin algoritmi: Jaettaessa että Käy peremmälle b, saadaan osamäärä c ja a r. Joten, suurin yhteinen jakaja että Y b on sama kuin b Y r. Tämä, kun otetaan huomioon seuraavat seikat: a = bc + r. Ymmärrämme sen paremmin soveltamalla tätä menetelmää esimerkkiin, joka on aiemmin esitetty kohdissa 216 ja 156.
216/156 = 1, loput 60
nyt jaetaan 156/60 = 2 lopun 36 kanssa
Jaamme jälleen 60/36 = 1 lopun 24 kanssa
Jaamme jälleen kerran 36/24 = 1 jäännöksellä 12
Ja lopuksi jaamme 24/12 = 2 jäännöksellä 0
Siksi suurin yhteinen jakaja on 12. Kuten voimme nähdä, meidän on jaettava, kunnes loppuosa on 0 ja viimeinen jakaja on GCF.
- Perustuu vähiten yleiseen moninkertaiseen: Numerot kerrotaan ja tulos jaetaan niiden pienimmällä yhteiskerralla (LCM).
Meidän on muistettava, että vähiten yhteinen moninkertainen (LCM) on pienin luku, joka täyttää ehdon olla moninkertainen kaikkien joukkoelementtien joukosta.
Eli palaten samaan esimerkkiin, voimme hajota seuraavasti:
216 = (3 3) * (2 3) ja 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Pienin yhteinen moninkertainen olisi: (3 3) * (2 3) * 13 * 17 * 7 = 334,152
Joten: GCD = 216 * 156 / 2,808 = 12
On syytä mainita, että tämä menetelmä toimii vain kahdella luvulla.