Hendra Jaya Napitupulu | Sifat-sifat GCD (3)

Sifat-sifat GCD (3)

GCD dari dua buah bilangan bulat $a$ dan $b$ sama dengan GCD dari $|a|$ dan $|b|$ . Rasanya pembuktian formal perlu diberikan agar tidak terjadi kebingungan dalam mencari GCD dari bilangan bulat negatif.

Buktikan bahwa $\gcd (a, b) = \gcd (|a|, |b|)$ dimana $a, b \in ℤ$

bukti

Misalkan $D$ adalah himpunan faktor-faktor persekutuan dari $a$ dan $b$ yang sudah disusun dari yang terkecil ke yang terbesar:

$D = {{−d}_{n}, \dots, {−d}_{3}, {−d}_{2}, {−d}_{1}, −1, 1, d_{1}, d_{2}, d_{3}, \dots, d_{n}}$

Semua anggota himpunan di atas, tidak perduli positif atau negatif, habis membagi $a$ dan $b$ .

Tidak hanya itu, semua anggota himpunan di atas, tidak perduli positif atau negatif, habis juga membagi $|a|$ dan $|b|$ . Artinya $D$ juga adalah himpunan faktor-faktor persekutuan dari $|a|$ dan $|b|$ .

Karena kedua pasangan memiliki himpunan faktor-faktor persekutuan yang sama, maka kedua pasangan pasti memiliki GCD yang sama.