Hendra Jaya Napitupulu | Sifat-sifat GCD (1)

Sifat-sifat GCD (1)

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

bukti

Misalkan:
$d = \gcd (a, b)$
$e = \gcd (a + k b, b)$

Ide utama pembuktian ini adalah membuktikan bahwa:

Jika $d$ habis membagi $e$ dan begitu juga sebaliknya $e$ habis membagi $d$ , maka $d = e$

Membuktikan d habis membagi e

Karena $d = \gcd (a, b)$ maka $d$ pasti habis membagi $a$ dan $b$ yaitu:
$a = d m$
$b = d n$

$a + k b$
$= d m + k d n$
$= d (m + k n)$

Terlihat jelas bahwa $d$ adalah salah satu faktor dari $a + k b$

Karena $a + k b$ dan $b$ keduanya mempunyai faktor $d$ , maka GCD dari $a + k b$ dan $b$ , yaitu $e$ , pasti juga mempunyai faktor $d$ .

Artinya $d$ pasti habis membagi $e$ .

Membuktikan e habis membagi d

Karena $e = \gcd (a + k b, b)$ maka $e$ pasti habis membagi $a + k b$ dan $b$ yaitu:
$a + k b = e m$
$b = e n$

$a$
$= e m - k b$
$= e m - k e n$
$= e (m - k n)$

Terlihat jelas bahwa $e$ adalah salah satu faktor dari $a$

Karena $a$ dan $b$ keduanya mempunyai faktor $e$ , maka GCD dari $a$ dan $b$ , yaitu $d$ , pasti juga mempunyai faktor $e$ .

Artinya $e$ pasti habis membagi $d$ .

Kesimpulan

Karena $d$ habis membagi $e$ dan begitu juga sebaliknya $e$ habis membagi $d$ , maka $d = e$