Sifat GCD (5)

Jika keduanya tidak $0$, maka nilai maksimum yang mungkin dari GCD dua buah bilangan bulat $a$ dan $b$ adalah $\min (\mathrm{|a|},\mathrm{|b|})$

$\gcd (a,b)\le \min (\mathrm{|a|},\mathrm{|b|})$ dimana $a,b\ne 0$ dan $a,b\in \mathbb{Z}$

Kasus maksimum, kasus $\gcd (a,b)=\min (\mathrm{|a|},\mathrm{|b|})$ terjadi jika dan hanya jika $a$ habis membagi $b$ atau $b$ habis membagi $a$.

Definisi

$\min (a,b)$ adalah sebuah fungsi yang mengembalikan nilai terkecil (minimum) di antara $a$ dan $b$

Bukti

Tanpa kehilangan sifat umum (without loss of generality), misalkan $\mathrm{|a|}\le \mathrm{|b|}$
Karena $\mathrm{|a|}\le \mathrm{|b|}$ maka $\min (\mathrm{|a|},\mathrm{|b|})=\mathrm{|a|}$
Berarti tujuan pembuktian adalah untuk membuktikan $\gcd (a,b)\le \mathrm{|a|}$

Misalkan $\gcd (a,b)=d$ maka $a$ pasti habis dibagi oleh $d$

Sekarang kalau diasumsikan $d>\mathrm{|a|}$ tentu saja $a$ tidak akan habis dibagi oleh $d$. Terjadi kontradiksi dan artinya asumsi ini pasti salah.

$\gcd (a,b)\le \mathrm{|a|}$
$\gcd (a,b)\le \min (\mathrm{|a|},\mathrm{|b|})$

Terbuktilah $\gcd (a,b)\le \min (\mathrm{|a|},\mathrm{|b|})$

Implikasi 1

Akan dibuktikan implikasi berikut: Jika $\gcd (a,b)=\min (\mathrm{|a|},\mathrm{|b|})$ maka $a$ habis membagi $b$.

$\gcd (a,b)=\min (\mathrm{|a|},\mathrm{|b|})$
$\gcd (a,b)=\mathrm{|a|}$

Karena $\mathrm{|a|}$ habis membagi $a$ dan $b$, maka $a$ pasti habis membagi $a$ dan $b$ juga.

Implikasi 2

Sekarang akan dibuktikan implikasi berikut: Jika $a$ habis membagi $b$ maka $\gcd (a,b)=\min (\mathrm{|a|},\mathrm{|b|})$

Jika $a$ habis membagi $b$ artinya $a$ adalah salah satu faktor persekutuan dari $a$ dan $b$. Karena $a$ bisa saja positif ataupun negatif, maka, untuk memastikan nilainya pasti positif, hanya $\mathrm{|a|}$ saja yang dimasukkan ke dalam faktor persekutuan positif dari $a$ dan $b$. Dan tentu saja $\mathrm{|a|}$ adalah faktor persekutuan positif terbesar.

$\gcd (a,b)=\mathrm{|a|}$
$\gcd (a,b)=\min (\mathrm{|a|},\mathrm{|b|})$

Kesimpulan

Pembuktian sudah lengkap dan memang betul:

$\gcd (a,b)\le \min (\mathrm{|a|},\mathrm{|b|})$ dimana $a,b\ne 0$ dan $a,b\in \mathbb{Z}$

$\gcd (a,b)=\min (\mathrm{|a|},\mathrm{|b|})$ terjadi jika dan hanya jika $a$ habis membagi $b$ atau $b$ habis membagi $a$.