Sifat GCD (6)

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

Ini adalah sifat GCD yang sering dipakai dalam menyelesaikan soal teori bilangan.

Contoh

Contoh 1

Carilah faktor persekutuan terbesar dari $582$ dan $27$

Menggunakan Teorema

Karena $582=15+21\cdot 27$ maka

$\gcd (582,27)=\gcd (15+21\cdot 27,27)$
$\gcd (582,27)=\gcd (15,27)$
$\gcd (582,27)=3$

Menggunakan Faktor

$582=2\cdot 3\cdot 97$
$27=3^3$

Dari faktor-faktor di atas, diperoleh $\gcd (582,27)=3$

Bukti

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

Ide utama pembuktian ini adalah membuktikan bahwa:

• $d$ habis membagi $e$ dan
• $e$ habis membagi $d$

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=dm$
$b=dn$

$a+kb=dm+kdn$
$a+kb=d(m+kn)$

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

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

Artinya $d$ pasti habis membagi $e$.

Membuktikan e habis membagi d

Karena $e=\gcd (a+kb,b)$ maka $e$ pasti habis membagi $a+kb$ dan $b$ yaitu:
$a+kb=em$
$b=en$

$a=em-kb$
$a=em-ken$
$a=e(m-kn)$

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$