Sifat GCD (4)
Jika setidaknya salah satunya tidak \( 0 \), maka nilai minimum yang mungkin dari GCD dua buah bilangan bulat \( a \) dan \( b \) adalah \( 1 \).
\( \gcd(a, b) \ge 1 \) dimana \( a, b \in \mathbb{Z} \)
Kasus minimum, yaitu kasus \( \gcd(a, b) = 1 \), terjadi jika dan hanya jika \( a \) dan \( b \) adalah dua bilangan yang relatif prima.
Definisi
Jika satu-satunya bilangan bulat positif yang habis membagi bilangan bulat \( a \) dan \( b \) adalah \( 1 \) maka \( a \) dan \( b \) adalah dua bilangan yang relatif prima (relatively prime) atau kadang juga disebut koprima (coprime).
bukti
Misalkan \( D \) adalah himpunan semua bilangan bulat positif yang habis membagi \( a \) dan \( b \)
Susun anggota himpunan \( D \) dari yang terkecil ke yang terbesar:
\( D = \{ 1, d_1, d_2, d_3, \cdots, d_n \} \)
Perhatikan bahwa anggota himpunan \( D \) yang terkecil pasti \( 1 \). Hal ini disebabkan oleh dua hal:
- Karena semua bilangan pasti habis dibagi oleh \( 1 \), maka \( 1 \) pasti ada di dalam \( D \)
- Karena tidak ada bilangan bulat positif yang lebih kecil dari \( 1 \)
Karena anggota terkecil himpunan \( D \) adalah \( 1 \), maka \( \gcd(a, b) \) tidak mungkin lebih kecil dari \( 1 \). Artinya, \( \gcd(a, b) \ge 1 \).
Kasus salah satunya 0
Bagaimana jika salah satu dari \( a \) atau \( b \) bernilai \( 0 \)?
Kasus ini sudah dibuktikan dalam sifat ini, yaitu pada corollary kedua.
Implikasi 1
Sekarang akan dibuktikan implikasi berikut: Jika \( \gcd(a, b) = 1 \), maka \( a \) dan \( b \) adalah dua bilangan yang relatif prima.
Tadi di atas sudah didefinisikan bahwa \( D \) adalah himpunan semua bilangan bulat positif yang habis membagi \( a \) dan \( b \).
Jika \( \gcd(a, b) = 1 \), artinya \( D \) hanya mempunyai satu buah anggota himpunan, yaitu \( 1 \) seperti di bawah ini:
\( D = \{ 1 \} \)
Akibatnya, satu-satunya bilangan bulat positif yang habis membagi \( a \) dan \( b \) adalah \( 1 \). Sesuai definisi, \( a \) dan \( b \) pastilah bilangan yang relatif prima.
Implikasi 2
Sekarang akan dibuktikan implikasi berikut: Jika \( a \) dan \( b \) adalah dua bilangan yang relatif prima, maka \( \gcd(a, b) = 1 \)
Karena satu-satunya bilangan bulat positif yang habis membagi \( a \) dan \( b \) adalah \( 1 \), maka \( D \) hanya mempunyai satu anggota seperti ini:
\( D = \{ 1 \} \)
Karena \( D \) hanya mempunyai satu buah anggota himpunan, yaitu \( 1 \), maka otomatis anggota terbesar himpunan \( D \) adalah \( 1 \) juga. Akibatnya, \( \gcd(a, b) = 1 \)
Kesimpulan
Karena kedua implikasi sudah dibuktikan maka pembuktian sudah lengkap dan memang betul:
Jika setidaknya salah satu dari \( a \) dan \( b \) tidak \( 0 \), maka \( \gcd(a, b) \ge 1 \) dimana \( a, b \in \mathbb{Z} \)
\( \gcd(a, b) = 1 \) terjadi jika dan hanya jika \( a \) dan \( b \) adalah dua bilangan yang relatif prima.
Contoh
Contoh 1
Buktikan bahwa \( 2 \) dan \( 3 \) adalah dua bilangan yang relatif prima.
Himpunan bilangan bulat positif positif yang habis membagi \( 2 \) dan \( 3 \) adalah \( \{ 1 \} \)
Karena anggota himpunan terbesar adalah \( 1 \), maka \( \gcd(2, 3) = 1 \)
Karena \( \gcd(2, 3) = 1 \), maka \( 2 \) dan \( 3 \) adalah dua bilangan yang relatif prima.
Contoh 2
Buktikan bahwa \( 4 \) dan \( 6 \) bukan dua buah bilangan yang koprima.
Himpunan bilangan bulat positif positif yang habis membagi \( 4 \) dan \( 6 \) adalah \( \{ 1, 2 \} \)
Karena anggota himpunan terbesar adalah \( 2 \), maka \( \gcd(4, 6) = 2 \)
Karena \( \gcd(4, 6) = 2 \), maka \( 4 \) dan \( 6 \) bukan dua buah bilangan yang koprima.