Hendra Jaya Napitupulu | Sifat-sifat GCD (5)

Sifat-sifat GCD (5)

Jika $a$ adalah sebuah bilangan bulat bukan $0$ , maka GCD dari $a$ dan $0$ adalah $|a|$

Walaupun sifat ini rasanya sudah sangat jelas, tetapi rasanya penting untuk memberikan bukti formal atas sifat GCD ini karena sifat ini akan dipakai sebagai kasus dasar (base case) dalam Algoritma Euclid.

Buktikan bahwa $\gcd (a, 0) = |a|$ dimana $a \neq 0$ dan $a \in ℤ$

bukti

Karena semua bilangan habis membagi $0$ , maka $\gcd (a, 0)$ hanya bergantung dari faktor terbesar $a$ .

Misalkan $A$ adalah himpunan faktor-faktor $a$ yang sudah disusun dari yang terkecil ke yang terbesar:

$A = {−a, \dots, {−a}_{3}, {−a}_{2}, {−a}_{1}, −1, 1, a_{1}, a_{2}, a_{3}, \dots, a}$

Jelas sekali terlihat bahwa faktor terbesar dari $a$ adalah bilangan positif $a$ . Memang betul $\gcd (a, 0) = |a|$