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:

  1. Karena semua bilangan pasti habis dibagi oleh \( 1 \), maka \( 1 \) pasti ada di dalam \( D \)
  2. 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.

Last updated: 5 October 2026