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).

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 $\left\{1\right\}$
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.

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,\dots ,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=\left\{1\right\}$

Artinya, $1$ adalah satu-satunya bilangan bulat positif yang habis membagi $a$ dan $b$. 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$ juga pasti akan menjadi seperti ini:

$D=\left\{1\right\}$

Karena $D$ hanya mempunyai satu buah anggota himpunan, yaitu $1$, maka otomatis anggota terbesar himpunan $D$ adalah $1$ juga. Dengan demikian, $\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.