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 |