Greatest Common Divisor

Greatest Common Divisor (GCD), atau biasa dikenal dengan nama Faktor Persekutuan Terbesar (FPB), didefinisikan sebagai berikut:

GCD dari dua buah bilangan bulat a dan b, dimana setidaknya salah satunya tidak nol, adalah bilangan bulat positif terbesar d yang habis membagi a dan b

Biasanya, notasi penulisan Greatest Common Divisor dari dua buah bilangan bulat a dan b adalah gcd(a,b)

Sebagai contoh, GCD dari 12 dan 20 adalah 4, yaitu, gcd(12,20)=4

GCD dari 0 dan 0 didefinisikan sebagai 0

gcd(0,0)=0

Contoh

Contoh 1

Carilah GCD dari 54 dan 24

Himpunan bilangan bulat positif yang habis membagi 54 adalah {1,2,3,6,9,18,27,54}
Himpunan bilangan bulat positif yang habis membagi 24 adalah {1,2,3,4,6,8,12,24}
Himpunan bilangan bulat positif yang habis membagi 54 dan 24 adalah {1,2,3,6}

Dengan demikian, gcd(54,24)=6

Contoh 2

Carilah GCD dari 48 dan −18

Himpunan bilangan bulat positif yang habis membagi 48 adalah {1,2,3,4,6,8,12,16,24,48}
Himpunan bilangan bulat positif yang habis membagi −18 adalah {1,2,3,6,9,18}
Himpunan bilangan bulat positif yang habis membagi 48 dan −18 adalah {1,2,3,6}

Dengan demikian, gcd(48,−18)=6

Contoh 3

Carilah GCD dari −60 dan 24

Himpunan bilangan bulat positif yang habis membagi −60 adalah {1,2,3,4,5,6,10,12,15,20,30,60}
Himpunan bilangan bulat positif yang habis membagi 24 adalah {1,2,3,4,6,8,12,24}
Himpunan bilangan bulat positif yang habis membagi −60 dan 24 adalah {1,2,3,4,6,12}

Dengan demikian, gcd(−60,24)=12

Contoh 4

Carilah GCD dari −15 dan −20

Himpunan bilangan bulat positif yang habis membagi −15 adalah {1,3,5,15}
Himpunan bilangan bulat positif yang habis membagi −20 adalah {1,2,4,5,10,20}
Himpunan bilangan bulat positif yang habis membagi −15 dan −20 adalah {1,5}

Dengan demikian, gcd(−15,−20)=5

Sifat

gcd(a,0)=|a| bukti
gcd(a,b)=gcd(b,a) bukti
gcd(a,b)=gcd(|a|,|b|) bukti
gcd(a,b)≥1 bukti
gcd(a,b)≤min(|a|,|b|) dimana a,b≠0 bukti
gcd(a+k⁢b,b)=gcd(a,b) bukti
gcd(a,b)=1 jika dan hanya jika gcd(a⁢b,a+b)=1 bukti

Last updated: 16 August 2026