Great Common Divisor (GCD)

Bagi sebagian Orang terutama yang masih “duduk” di bangku sekolah (SD/SMP/SMA)  mungkin cukup asing dengan istilah “Great Common Divisor” atau GCD,,,, (saya bilang sebagian lho, bukan seluruhnya...)
Tapi saya yakin kalo dengan istilah “Faktor Persekutuan Terbesar” atau FPB anak SD-pun pasti mengetahuinya…. Padahal FPB itu adalah sebutan lain Untuk GCD, tapi alangkah baiknya mulai sekarang kita biasakan dengan istilah GCD karena lebih Internasional. (bukan berarti tidak cinta Indonesia Lho, hhe)
Selain GCD, FPB masih punya “nama” lain, yaitu Greatest Common Factor (GCF) dan Highest Common Factor (HCF). Tapi semua sama aja kok.

DEFINISI GCD (FPB)
Great Common Divisor (GCD) dari dua bilangan adalah bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan itu.

Contoh 1:
Faktor dari 12 adalah 1, 2, 3, 4, 6, 12
Faktor dari 20 adalah 1, 2, 4, 5, 10, 20
Karena 4 merupakan faktor dari 12 dan 20 (faktor sekutu) dan merupakan faktor yang terbesar, maka GCD (12,20) = 4

CARA MENENTUKAN GCD:

Ada beberapa cara dalam menentukan GCD, diantaranya:

Dengan mengubah kedalam bentuk perkalian bilangan prima berpangkat. Kemudian dipilih pangkat terendah.
Contoh 2:
Tentukan GCD (2520,2646)
Jawab:
2520 = 2³×3²×5×7
2646 = 2×3²×7²
Dari perkalian-perkalian diatas, untuk bilangan prima yang sama kita ambil yang pangkatnya terendah.
Jadi, GCD(2520,2646)=2×3²×7=126

Dengan menggunakan algoritma Euclidean.
Konsep mencari GCD dengan menggunakan Algoritma Euclidean adalah sebagai berikut:
Misal kita ingin mencari GCD dari dua buah bilangan (kita misalkan bilangan tersebut adalah A dan B, dimana A>B)
Kita bagi bilangan yang lebih besar (A) dengan bilangan yang kecil (B), jika tidak bersisa (sisa = 0) maka B adalah GCD-nya. Jika bersisa, maka lakukan pembagian lagi, maka remainder (sisa) terakhir adalah GCD-nya. Jika sisa terakhir = 0, maka GCD-nya adalah bilangan sebelumnya.

Contoh 3:
Tentukan GCD (2520,2646)

Jawab:
2646=2520×1+126
2520=126×20+0
Karena sisa akhir adalah 0, maka GCD-nya 126

Contoh 4:
Tentukan GCD (76520,13422)

Jawab:
76520=13422×5+9410

13422=9410×1+4012
9410=4012×2+1386
4012=1386×2+1240
1386=1240×1+146
1240=146×8+72
146=72×2+2
72=2×36+0
jadi GCD (76520,13422)=2

Contoh 5:
Tentukan GCD(3080,2420) dengan menggunakan Algoritma Euclidean dan dengan perkalian Bilangan prima.

jawab:
Menggunakan Algoritma Euclidean;
3080=2420x1+660
2420=660x3+440
660=440x1+220
440=220x2+0
maka GCD(3080,2420) adalah 220

Menggunakan Perkalian bil. prima;
dengan menggunakan pohon faktor diperoleh
3080=2³ x 5 x 7 x 11
2420=2² x 5 x 11²
maka GCD(3080,2420) adalah 2² x 5 x 11 = 220

Sumber https://www.m4th-lab.net/

Bagikan Artikel ini