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)
Baca Juga
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
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
Via : http://www.foldersoal.com>
Belum ada Komentar untuk "Great Common Divisor (GCD)"
Posting Komentar