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) = \lvert a \rvert \) bukti
\( \gcd(a, b) = \gcd(b, a) \) bukti
\( \gcd(a, b) = \gcd(\lvert a \rvert, \lvert b \rvert) \) bukti
\( \gcd(a, b) \ge 1 \) bukti
\( \gcd(a, b) \le \min(\lvert a \rvert, \lvert b \rvert) \) dimana \( a, b \ne 0 \) bukti
\( \gcd(a + kb, b) = \gcd(a, b) \) bukti
Semua faktor persekutuan positif dari \( a \) dan \( b \) habis membagi \( \gcd(a, b) \) bukti

Last updated: 5 October 2026