Sifat GCD (2)

$\gcd (a,b)=\gcd (b,a)$ dimana $a,b\in \mathbb{Z}$

Sifat ini adalah sifat komutatif GCD dan sangat sering digunakan dalam mengoperasikan GCD. Berikut diberikan beberapa contoh pemakaian sifat ini dan bukti kebenaran sifat ini.

Contoh

Contoh 1

Bandingkanlah $\gcd (6,8)$ dengan $\gcd (8,6)$

Himpunan faktor persekutuan positif dari $6$ dan $8$ adalah $\{1,2\}$
Karena anggota himpunan terbesar adalah $2$, maka $\gcd (6,8)=2$

Himpunan faktor persekutuan positif dari $8$ dan $6$ adalah $\{1,2\}$
Karena anggota himpunan terbesar adalah $2$, maka $\gcd (8,6)=2$

Jadi, $\gcd (6,8)=\gcd (8,6)$

Contoh 2

Bandingkanlah $\gcd (\mathrm{-8},12)$ dengan $\gcd (12,\mathrm{-8})$

Himpunan faktor persekutuan positif dari $\mathrm{-8}$ dan $12$ adalah $\{1,2,4\}$
Karena anggota himpunan terbesar adalah $4$, maka $\gcd (\mathrm{-8},12)=4$

Himpunan faktor persekutuan positif dari $12$ dan $\mathrm{-8}$ adalah $\{1,2,4\}$
Karena anggota himpunan terbesar adalah $4$, maka $\gcd (12,\mathrm{-8})=4$

Jadi, $\gcd (\mathrm{-8},12)=\gcd (12,\mathrm{-8})$

Contoh 3

Bandingkanlah $\gcd (\mathrm{-3},0)$ dengan $\gcd (0,\mathrm{-3})$

Karena semua bilangan habis membagi $0$, maka faktor persekutuan positif dari $\mathrm{-3}$ dan $0$ hanya bergantung pada faktor positif dari $\mathrm{-3}$ yaitu $\{1,3\}$
Karena anggota himpunan terbesar adalah $3$, maka $\gcd (\mathrm{-3},0)=3$

Sama seperti di atas.
Karena semua bilangan habis membagi $0$, maka faktor persekutuan positif dari $0$ dan $\mathrm{-3}$ hanya bergantung pada faktor positif dari $\mathrm{-3}$ yaitu $\{1,3\}$
Karena anggota himpunan terbesar adalah $3$, maka $\gcd (0,\mathrm{-3})=3$

Jadi, $\gcd (\mathrm{-3},0)=\gcd (0,\mathrm{-3})$

Contoh 4

Bandingkanlah $\gcd (\mathrm{-5},\mathrm{-10})$ dengan $\gcd (\mathrm{-10},\mathrm{-5})$

Himpunan faktor persekutuan positif dari $\mathrm{-5}$ dan $\mathrm{-10}$ adalah $\{1,5\}$
Karena anggota himpunan terbesar adalah $5$, maka $\gcd (\mathrm{-5},\mathrm{-10})=5$

Himpunan faktor persekutuan positif dari $\mathrm{-10}$ dan $\mathrm{-5}$ adalah $\{1,5\}$
Karena anggota himpunan terbesar adalah $5$, maka $\gcd (\mathrm{-10},\mathrm{-5})=5$

Jadi, $\gcd (\mathrm{-5},\mathrm{-10})=\gcd (\mathrm{-10},\mathrm{-5})$

Bukti

Misalkan $D$ adalah himpunan semua bilangan bulat positif yang habis membagi $a$ dan juga habis membagi $b$. Kemudian, kalau anggota himpunan $D$ disusun dari yang terkecil sampai yang terbesar diperoleh:

$D=\{d_1,d_2,d_3,\dots ,d_k\}$

Cukup jelas bahwa anggota himpunan terbesar $D$ adalah $d_k$
Artinya $\gcd (a,b)=d_k$

Sekarang, misalkan $E$ adalah himpunan semua bilangan bulat positif yang habis membagi $b$ dan juga habis membagi $a$. Tentu saja anggota himpunan $E$ akan sama persis dengan anggota himpunan $D$, yaitu:

$E=\{d_1,d_2,d_3,\dots ,d_k\}$

Karena himpunan $E$ sama dengan himpunan $D$, maka pasti anggota himpunan terbesar dari $E$ adalah $d_k$ juga.
Artinya $\gcd (b,a)=d_k$

Dengan demikian, memang betul sifat komutatif GCD. Yaitu $\gcd (a,b)=\gcd (b,a)$