Sifat GCD (7)

$\gcd (a,b)=1$ jika dan hanya jika $\gcd (ab,a+b)=1$ dimana $a,b\in \mathbb{Z}$

Kadangkala, dalam menyelesaikan soal teori bilangan, ditemukan fakta seperti $\gcd (ab,a+b)=1$. Perlu diketahui bahwa kedua pernyataan ini, $\gcd (a,b)=1$ dan $\gcd (ab,a+b)=1$, adalah pernyataan yang ekuivalen.

Selain itu, sifat ini perlu diketahui karena ekspresi $a+b$ dan $ab$ adalah dua ekspresi yang sangat melekat dengan persamaan kuadrat.

Contoh

Contoh 1

Tunjukkan bahwa akar-akar dari persamaan $x^2-11x-210=0$ adalah dua bilangan yang relatif prima.

Menggunakan Teorema

Misalkan akar-akar dari persamaan kuadrat di atas adalah $a$ dan $b$, maka:
$a+b=\mathrm{-11}$
$ab=\mathrm{-210}$

$\gcd (\mathrm{-11},\mathrm{-210})=\gcd (11,210)$
$\gcd (\mathrm{-11},\mathrm{-210})=1$

Karena $\gcd (\mathrm{-11},\mathrm{-210})=1$ maka pasti $\gcd (a,b)=1$

Mencari Akar

$x^2-11x-210=0$
$(x-21)(x+10)=0$

Akar-akar dari persamaan kuadrat di atas adalah $x_1=21$ dan $x_2=\mathrm{-10}$

$\gcd (21,\mathrm{-10})=\gcd (21,10)$
$\gcd (21,\mathrm{-10})=1$

Bukti

Karena ini adalah biimplikasi (jika dan hanya jika), maka ada dua implikasi yang harus dibuktikan:

1. Jika $\gcd (a,b)=1$ maka $\gcd (ab,a+b)=1$
2. Jika $\gcd (ab,a+b)=1$ maka $\gcd (a,b)=1$

Membuktikan implikasi 1

Implikasi 1 akan dibuktikan melalui kontradiksi.

Asumsikan $\gcd (ab,a+b)=k$ dimana $k>1$

Karena $\gcd (ab,a+b)=k$ maka $k$ pasti habis membagi $ab$ dan $a+b$.

Perhatikan ekspresi $ab$. Karena $k$ habis membagi $ab$ maka setidak-tidaknya salah satu faktor dari $a$ atau $b$ adalah $k$ . Tanpa menghilangkan sifat umum (without loss of generality), anggap saja $k$ adalah faktor dari $a$. Artinya $a=km$

Sekarang, perhatikan ekspresi $a+b$. Karena $k$ habis membagi $a+b$ maka $a+b=kn$

$a+b=kn$
$b=kn-a$
$b=kn-km$
$b=k(n-m)$

Terlihat jelas bahwa ternyata $k$ juga adalah faktor dari $b$.

Sekarang, karena $a$ dan $b$ dua-duanya mempunyai faktor $k$, maka setidak-tidaknya GCD dari $a$ dan $b$ adalah $k$. Karena tadi di awal diasumsikan $k>1$ maka terjadi kontradiksi. Artinya, asumsi yang dibuat di awal salah dan $\gcd (ab,a+b)$ haruslah $1$.

Membuktikan implikasi 2

Implikasi 2 juga akan dibuktikan melalui kontradiksi.

Asumsikan $\gcd (a,b)=k$ dimana $k>1$

Karena $\gcd (a,b)=k$ maka baik $a$ dan $b$ kedua-duanya pasti mempunyai faktor $k$. Katakanlah $a=km$ dan $b=kn$

Perhatikan ekspresi $ab$:
$ab=km\cdot kn$
$ab=k^{2}mn$

Sekarang, perhatikan ekspresi $a+b$:
$a+b=km+kn$
$ab=k(m+n)$

Terlihat jelas bahwa baik $ab$ dan $a+b$ keduanya mempunyai faktor $k$. Artinya, GCD $ab$ dan $a+b$ setidak-tidaknya bernilai $k$. Karena $k>1$ maka terjadi kontradiksi. Artinya, asumsi yang dibuat di awal salah dan $\gcd (a,b)$ haruslah $1$.

Kesimpulan

Karena kedua implikasi sudah dibuktikan. Maka terbuktilah biimplikasi $\gcd (a,b)=1$ jika dan hanya jika $\gcd (ab,a+b)=1$